684. Redundant Connection
## 思路
UnionFind
照顺序把点连起来 如果在同一个GROUP表示有环 -> 回传该edge
## Code
```cpp
class UnionFind {
public:
UnionFind(int n) {
rank_.resize(n, 1);
root_.resize(n, 0);
for (int i=0; i<n; ++i) {
root_[i] = i;
}
}
int findP(int x) {
if (root_[x] != x) {
root_[x] = findP(root_[x]);
}
return root_[x];
}
bool unionP(int x, int y) {
int rx = findP(x), ry = findP(y);
if (rx == ry) return false;
if (rank_[rx] >= rank_[ry]) {
root_[ry] = rx;
rank_[rx] += rank_[ry];
} else {
root_[rx] = ry;
rank_[ry] += rank_[rx];
}
return true;
}
private:
vector<int> root_;
vector<int> rank_;
};
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
UnionFind uf(n+1);
for (auto edge: edges) {
if (!uf.unionP(edge[0], edge[1])) {
return edge;
}
}
return {};
}
};
```