原题链接：

684. 冗余连接

https://leetcode.cn/problems/redundant-connection/description/

完成情况：

解题思路：

这段代码是一个解决问题的类，其中实现了一个并查集数据结构。在初始化时，节点数量被设定为1005，然后进行并查集的初始化。并查集包括了寻找根节点、合并两个节点、判断两个节点是否属于同一个集合等功能。

• find(int u)函数用于找到节点u的根节点。
• join(int u, int v)函数用于将节点v和节点u所在的集合合并。
• same(int u, int v)函数用于判断节点u和节点v是否属于同一个集合。

最后，findRedundantConnection(int[][] edges)函数遍历边数组，对每条边进行判断：如果边的两个节点已经属于同一个集合，则返回这条边；否则将这两个节点合并到同一个集合中。最终返回一条导致环路的冗余边。

这段代码实现了一个简单的并查集，用于找到导致环路的冗余边。

参考代码：

package 代码随想录.并查集;public class _684冗余连接_图to树 {//n == edges.length//3 <= n <= 1000//直接拉满int n = 1002;  //全局变量N个节点int [] fatherPaths = new int[n]; //每个节点都试着去寻找上层路径，那么最终这样一个结构就会形成一棵树public _684冗余连接_图to树(int n, int[] fatherPaths) {this.n = n;this.fatherPaths = fatherPaths;
//        int n = 1002;  //全局变量N个节点
//        int [] fatherPaths = new int[n]; //每个节点都试着去寻找上层路径，那么最终这样一个结构就会形成一棵树//初始化并查集for (int i = 0; i < n; i++) {fatherPaths[i] = i;}}/*** 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。* 本来是一个图，然后请你删除一条边，使原来的图转变为成一棵树* 如果有多种情况，那么就返回数组 edges 中最后出现的那条边。** @param edges 指示出来所有的连接边* @return*/public int[] findRedundantConnection(int[][] edges) {for (int i = 0; i < edges.length; i++) {if (isSameFather(edges[i][0],edges[i][1])){ //是否是同一条边return edges[i];}else{//将两条边连接起来joinPath(edges[i][0],edges[i][1]);}}return null;}/**** @param sourceA* @param sourceB*/private void joinPath(int sourceA, int sourceB) {sourceA = findNode(sourceA);sourceB = findNode(sourceB);if (sourceA == sourceB)   return;fatherPaths[sourceB] = sourceA;}/**** @param sourceNode* @return*/private int findNode(int sourceNode) {if (sourceNode == fatherPaths[sourceNode]){return sourceNode;}fatherPaths[sourceNode] = findNode(fatherPaths[sourceNode]);return fatherPaths[sourceNode];}/**** @param nodeA* @param nodeB* @return*/private boolean isSameFather(int nodeA, int nodeB) {nodeA = findNode(nodeA);nodeB = findNode(nodeB);return nodeA == nodeB;}
}

错误经验吸取