rank优化的并查集，顺序遍历edges，如果边在同一连通分量，说明这条边是冗余的。
时间复杂度：O（n）
空间复杂度：O（n）
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
Disjoint_Set disjoint_Set = new Disjoint_Set(n+1);
for(int[] path : edges) {
int from = path[0];
int to = path[1];
if(!disjoint_Set.isSame(from, to)) {
disjoint_Set.union(from, to);
}else {
return path;
}
}
return new int[] {};
}
class Disjoint_Set {
int[] parents;
int[] rank;
public Disjoint_Set(int n) {
parents = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parents[i] = i;
rank[i] = 1; //初始每个集合大小为1
}
}
public int find(int x) {
if(parents[x] == x)
return x;
return find(parents[x]);
}
public boolean isSame(int x, int y) {
return find(x) == find(y);
}
public void union(int x, int y) {
int p1 = find(x);
int p2 = find(y);
if(p1 == p2) //所属同一集合,直接返回
return ;
if(rank[p1] < rank[p2]) { //树矮的连接到树高的，rank不变
parents[p1] = p2;
}else if (rank[p1] > rank[p2]){
parents[p2] = p1;
}else { //只有树高相同时,连接的时候,连接的根节点rank+1
parents[p2] = p1;
rank[p1]++ ;
}
return;
}
}
}