并查集算法

什么叫并查集

顾名思义并查集指的是，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。简而言之就是将不相交的区间进行合并，并且进行查找。

class UnionFindSet:
    def UnionFindSet(n):
        parents = [0,1...n] # 记录每个元素的parent即根节点 先将它们的父节点设为自己
        ranks =[0,0...0]    # 记录节点的rank值
    
    # 如下图 递归版本 路径压缩(Path Compression)
    # 如果当前的x不是其父节点，就找到当前x的父节点的根节点(find(parents[x])) 并将这个值赋值给x的父节点
    def find(x):
        if ( x !=parents[x]): # 注意这里的if
            parents[x] = find(parents[x])
        return parents[x]

    # 如下图 根据Rank来合并(Union by Rank)
    def union(x,y):
        rootX = find(x) # 找到x的根节点rootX
        rootY = find(y) # 找到y的根节点rootY
        #取rank值小的那个挂到大的那个节点下面，此时两个根节点的rank值并没有发生变化，还是原来的值
        if(ranks[rootX]>ranks[rootY]): parents[rootY] = rootX 
        if(ranks[rootX]<ranks[rootY]): parents[rootX] = rootY
        # 当两个rank值相等时，随便选择一个根节点挂到另外一个跟节点上，但是被挂的那个根节点的rank值需要+1    
        if(ranks[rootX] == ranks[rootY] ):
            parents[rootY] = rootX
            ranks[rootY]++

注意find()这里会进行一个压缩，比如你的集合连接顺序是 1-》2-》3-》4
这时候会进行递归查找，会一直查找到根节点，然后赋值给子节点的parent，让他直接指向根节点。1-》4，2-》4，3-》4；所有的子节点都会指向根节点。
例子：leetocde 684. 冗余连接

public int[] findRedundantConnection(int[][] edges) {
        if (edges == null || edges.length == 0) return new int[]{0, 0};
        int n = edges.length + 1; //注意此处下标多放一个
        UnionFind unionSet = new UnionFind();
        unionSet.intValue(n);
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            unionSet.union(x,y);
        }
        return unionSet.result;
    }
public class UnionFind {
    public int [] result;
    //声明一个parent 数组
    public int [] parent;

    public void intValue(int n){
        parent = new int[n];
        //由于区间的最大值不会超过N，我们可以把区间的每一个节点的初始父节点指向自己
        // ，代表他是一个独立的节点方便之后的合并
        for (int i = 0;i<n;i++){
            parent[i] = i;
        }
    }
    //主要方法
    //意思是，我要一直找，一直找到当前这个节点的根节点，把它当作父节点
    //为什么要这么做？因为要判断两个节点是否在一颗树上，只有判断他们的根节点是否是一个就可以，
    public int find(int x){
        if (x != parent[x]){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    //主要方法合并
    //合并两个节点如果互不相干，选取其中一个当作另外一个的父节点。
    public void union(int x,int y){
        int rootX = find(x);
        int rootY = find(y);
        //他们已经被连通过了，所以这一条边是冗余的
        if (rootX == rootY){
            result = new int[]{x,y};
        }else {
            //没有连通过，就选取其中一个的父节点，当作另外一个的父节点，进行合并
            parent[rootX] = rootY;
        }

    }

}