684. 冗余连接 - Java 并查集

原题地址：https://leetcode.cn/problems/redundant-connection/

题解

这道题是一道典型的并查集

我们创建一个dsu的类，包含一个int数组pa，其中pa[i]为节点i的父节点，并规定根节点的父节点为自身。

初始状态下，并查集中所有节点都单独为一棵树，pa[i]=i

查找操作：

对于任何一个节点x，不断地顺着pa数组向上搜索直到根节点，如果对于两个节点x和y有find(x)==find(y)则说明两个点在同一棵树内

合并操作：

由于并查集中的树是多叉树，我们可以直接将x的根节点的父节点重设为y的根节点

对于树而言，树的每一个节点到另一个节点的路径都是唯一的，也就是说不存在两个路径使得节点x和节点y都能在同一个连通分量中找到。遍历edges，根据边的两端将两个节点合并，如果某条边的两个节点已经在同一连通分量了，则说明这条边为多余边，返回即可

时间复杂度：O(NlogN)

空间复杂度：O(N)

class Solution {
    class dsu{
        int[] pa;
        dsu(int size){
            pa=new int[size+1];
            for (int i=0;i<pa.length;i++)pa[i]=i;
        }
        int find(int x){
            //路径压缩，直接将该树的所有节点全设为根节点的第一层子节点，节省查找时间
            return pa[x]==x?x:(pa[x] = find(pa[x]));
        }
        void union(int x,int y){
            pa[find(x)]=find(y);
        }
    }
    public int[] findRedundantConnection(int[][] edges) {
        dsu forest=new dsu(edges.length);
        for (int i=0;i<edges.length;i++){
            if(forest.find(edges[i][0])==forest.find(edges[i][1]))return edges[i];
            forest.union(edges[i][0],edges[i][1]);
        }
        return null;
    }
}