本文共 1324 字，大约阅读时间需要 4 分钟。
| element | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| parent | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
现在，“并”的操作可以这样来描述：观察第一个点对(4,3)，于是先找到点4和3，发现所在组别不一样，再将点4和3的组别都变成3（当然都变成4也行，这个随意设计），然后就产生了如下的表：
| element | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| parent | 0 | 1 | 2 | 3 | 3 | 5 | 6 | 7 | 8 | 9 |
而“查”的操作其实就是“并”操作的第一步：找到点对中两个点所在的组别，看是否相同。也就是说，并查集的两类基本操作中，都涉及了“根据点找组别”的过程，因此我们先给出一个高效的“查”的算法。我把它叫做Quick-Find 算法。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。class Solution { public int[] findRedundantConnection(int[][] edges) { int[] re=new int[2]; DFS dfs=new DFS(edges.length); dfs.union(edges[0][0]-1,edges[0][1]-1); for(int i=1;i 此题使用并查集解决。对于同一棵树的所有节点来说，都拥有共同的祖先节点。因此，判断冗余连接的条件即为，判断新加入的边，两个节点是否有共同的祖先。
（1）如果有共同的祖先，则说明这条边是冗余的边 （2）如果没有共同的祖先，则说明这两条边并未加入树中，因此进行合并操作 循环边的记录，获取最后出现的冗余边，就是答案。转载地址：http://jyhli.baihongyu.com/