代码随想录 684.冗余连接

这道题也是并查集基础题目。

1.并查集可以解决的问题：

（1）判断两个节点是否在一个集合。

（2）将两个节点添加到一个集合中。

2.题目要求：对于一个无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树（即，只有一个根节点）。如果有多个答案，则返回二维数组中最后出现的边。

3.思路：可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即同一个根节点）。

（1）如下图所示，节点a和节点b不在同一个集合，那么就可以将两个节点连接在一起。

（2）如果边的两个节点已经出现在同一个集合里，则说明这条边的两个节点已经连在一起了，再加入这条边一定就出现环了，如下图所示。

4.注意：题目已说明该图是在树的基础上添加一条边得到，因此只会有一条冗余边，因此可以在遇到同一个根的两个节点后直接返回即可。

附代码：

class Solution { private int[] p; public int[] findRedundantConnection(int[][] edges) { int n = edges.length; p = new int[n]; for(int i = 0;i < n;i++){ p[i] = i; } for(int i = 0;;i++){ //无限循环，会一直执行到找到冗余边并返回，所以该方法一定有返回值（因为树的性质保证了该方法一定有一条冗余边） //若加上i < n条件，则编译器会认为如果循环内所有if(pa == pb)条件都不满足，那么循环会正常结束，此时循环结束后就没有返回值 //编译器在编译时只做静态代码分析，不执行程序逻辑推理 //编译器认为条件判断里的return只是可能返回，若加上i < n，有限循环中还需要在下面加一个return条件 int pa = find(edges[i][0] - 1); //因为节点编号从1开始，所以要 - 1做数组映射 int pb = find(edges[i][1] - 1); if(pa == pb){ return edges[i]; } p[pa] = pb; } } private int find(int x){ if(p[x] != x){ p[x] = find(p[x]); } return p[x]; } }