java数据结构与算法刷题-----LeetCode684. 冗余连接
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;//顶点个数
int[] parent = new int[n + 1];//并查集中下标从1开始
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
//遍历每个顶点的边的信息
for (int i = 0; i < n; i++) {
int[] edge = edges[i];//获取顶点i的边
int node1 = edge[0], node2 = edge[1];//获取两条边相邻的顶点
if (find(parent, node1) != find(parent, node2)) {//如果和顶点i都不属于同一个集合（连通分量）
union(parent, node1, node2);//说明这条边不会导致环的出现，将两个顶点加入并查集
} else {//如果属于同一个集合，说明人家两个顶点已经间接连接一起了，现在你这条边居然又把我俩直接连接了起来
return edge;//此边是构成环的罪魁祸首，将其返回
}
}
return new int[0];//无结果返回空
}
//并查集代码，合并
public void union(int[] parent, int index1, int index2) {
//合并index1和index2的步骤为：找到index1的祖先，然后找到index2的祖先
//让index1的祖先指向index2的祖先，完成两个集合的合并。
parent[find(parent, index1)] = find(parent, index2);
}
//从parent中查找index的祖先
public int find(int[] parent, int index) {
if (parent[index] != index) {//如果index不是自己指向自己，说明它自己不是集合中的根节点（祖先），他也有自己的祖先
parent[index] = find(parent, parent[index]);//不断找到其祖先，然后将其祖先记录到parent[index]位置，保证parent[index]只要find一次，就必须指向index的祖先
}
return parent[index];//返回自己的祖先
}
}