并查集

并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。可以求解一些图相关的问题（连通分量）。

并查集森林是一种将每一个集合以树的形式表示的数据结构，其中每个结点都保存着到他父节点的引用。在并查集森林中，每个集合的代表即是集合的根节点。“查找”根据其父节点的引用向根行进直到到底树根。“联合”将两棵树合并到一起，这通过将一棵树的根连接到另一棵树的根。

class UnionSet{
    int[] parent;
    //初始化并查集,每个结点自成一个集合
    void UnionSet(int n){
        parent=new int[n];
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
    }
    //递归查找根节点
    int find(int x){
        if(parent[x]==x) return x;
        else return find(parent[x]);
    }
    //将x,y所在集合合并
    void union(int x,int y){
        int xRoot = find(x);
        int yRoot = find(y);
        parent[xRoot] = yRoot;
    }
}

上述方法可能会导致严重的不平衡，下面介绍优化的方法。

按秩合并

按秩合并总是将更小的树连接到更大的树上，秩代表树的深度，单元素的树秩为0，当两颗秩为r的树合并时秩为r+1.

class UnionSet{
    int[] parent;
    int[] rank;

    void UnionSet(int n){
        parent=new int[n];
        rank=new int[n];
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
    }

    int find(int x){
        //操作相同
    }

    void union(int x,int y){
        int xRoot = find(x);
        int yRoot = find(y);
        if(rank[xRoot] > rank[yRoot]){
            parent[yRoot] = xRoot;
        }else if(rank[xRoot] < rank[yRoot]){
            parent[xRoot] = yRoot;
        }else{
            parent[xRoot] = yRoot;
            rank[yRoot] += 1; 
        }
    }
}

路径压缩

将每个结点直接连接到根节点上

int find(int x){
    if(parent[x]!=x){
        parent[x]=find(parent[x]);
    }
    return parent[x];
}

---