并查集

· · 个人记录

并查集

2023716update
原理：让i所在集合和j所在集合合并（将i，j根节点连边）
主要用于解决元素分组的问题
管理一系列不相交的集合
操作：
合并(union):把两个不相交的集合合并为一个集合
查询(find):查询两个元素是否在同一个集合中

朴素版本

初始化

int fa[maxn];
void init(int n)
{
    for(inti=1;i<=n;i++)
        fa[i] = i;
        //所有的父节点都是自己
}

查询

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

合并

void merge(int a,int b)
{
    fa[find(a)] = find(b);
}
tip：连边：让一个成为另一个的father

Code：

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int fa[N];
int gte_root(int x){//深搜找根 
    if(fa[x]==x) return x;//如果找到了根节点 那么return 
    return get_root(fa[x]);
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) fa[i]=i;//所有点都是根，所有点的父亲都是自己 
    for(int i=1;i<=m;i++){
        int tp;scanf("%d",&tp);
        if(tp==1){
            int x,y;scanf("%d%d",&x,&y);
            int rootx=get_root(x);//找代表
            int rooty=get_root(y); 
            if(rootx!=rooty){
                fa[rootx]=rooty;//fa[rooty]=rootx 
            }
        }
        if(tp==2){
            int x,y;scanf("%d%d",&x,&y);
            int rootx=get_root(x);//找代表
            int rooty=get_root(y);
            if(rootx==rooty) puts(" ");
            else puts(" ");
        }
    } 
}
/*总复杂度O(n^2)

（1）启发式合并（子树大的为father）

ps:感谢伟大而又智慧的计算机科学先驱

Code：

#include<iostream>
using namespace std;

int fa[100100];
int size[100100];//以x为根的子树大小 

int get_root(int x){//找根函数 
    if(fa[x]==x)return x;//x就是根！
    return get_root(fa[x]); //跳父亲。我的根就是我父亲的根 
}

int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i,size[i]=1;//一开始，所有点都是根，所有点的爸爸都是他自己 
    for(int i=1;i<=m;i++){
        int tp;cin>>tp;
        if(tp==1){
            int x,y;cin>>x>>y;
            int rootx=get_root(x);//找根（代表） 
            int rooty=get_root(y);
            //if(rootx==rooty)//啥也不用干 
            if(rootx!=rooty){
//              fa[rootx]=rooty;
//              fa[rooty]=rootx;
                if(size[rootx]>size[rooty]){//rootx的子树大 
                    fa[rooty]=rootx;//rootx的子树大，rootx当爸爸 
                    size[rootx]+=size[rooty];//维护size，rootx多了rooty这个子树 
                }else{//rooty的子树大 
                    fa[rootx]=rooty;
                    size[rooty]+=size[rootx];
                }
            }
        }
        if(tp==2){//查询 
            int x,y;cin>>x>>y;
            int rootx=get_root(x);//找根（代表） 
            int rooty=get_root(y);
            if(rootx==rooty)puts("认识！");//看看根（代表）是否是同一个人 
            else puts("不认识！"); 
        }
    }
}

（2）按秩合并（根节点深的当father）

需额外维护一个dep[x]数组，表示x的子树深度
我们应该把简单的树往复杂的树上合并
因为这样合并后，
到根节点距离变长的节点个数比较少。

我们用一个数组rank[]记录每个根节点对应的树的深度。
（如果不是根节点,其rank相当于以它作为根节点的子树的深度）
一0开始，把所有元素的rank（秩）设为1
合并时比较两个根节点，
把rank较小者往较大者上合并。

路径压缩和按秩合并如果一起使用，时间复杂度接近O(n),但是很可能会破坏rank的准确性。

初始化

void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}

合并

inline void merge(int i, int j)
{
    int x = find(i), y = find(j);    //先找到两个根节点
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;
        //如果深度相同且根节点不同，则新的根节点的深度+1
}
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int fa[N];
int size[N]; 
int gte_root(int x){//深搜找根 
    if(fa[x]==x) return x;//如果找到了根节点 那么return 
    return get_root(fa[x]);
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) fa[i]=i;//所有点都是根，所有点的父亲都是自己 
    for(int i=1;i<=m;i++){
        int tp;scanf("%d",&tp);
        if(tp==1){
            int x,y;scanf("%d%d",&x,&y);
            int rootx=get_root(x);//找代表
            int rooty=get_root(y); 
            if(rootx!=rooty){
                fa[rootx]=rooty;////fa[rooty]=rootx 
                if(size[rootx]>size[rooty]){//rootx子树大 
                    fa[rooty]=rootx;
                    size[rootx]+=size[rooty];//维护更新 
                }
                else{
                    fa[rootx]=rooty; 
                    size[rooty]+=size[rootx];
                } 
            }
        }
        if(tp==2){//查询 
            int x,y;scanf("%d%d",&x,&y);
            int rootx=get_root(x);//找代表
            int rooty=get_root(y);
            if(rootx==rooty) puts(" ");
            else puts(" ");
        }
    } 
}
/*总复杂度O(nlogn)

（3）路径压缩

原理不同：不改变合并过程，在get_root时把经过每个点的father直接变成根
既然我们只关心一个元素对应的根节点，那我们希望每个元素到根节点的路径尽可能短，最好只需要一步
如何实现？
在查询过程中，把沿途每个点的父亲都设为根节点

int find(int x)//路径压缩
{
    if(x == fa[x]) return x;
    else fa[x] = find(fa[x]),return fa[x]; 
}
//可简化为
int find(int x)
{
    return x == fa[x]?x:(fa[x] = find(fa[x]));
}

Code：

#include<iostream>
using namespace std;

int fa[100100];

/*
int get_root(int x){//找根函数 
    //if(fa[x]==x)return x;//x就是根！
    //return get_root(fa[x]); //跳父亲。我的根就是我父亲的根 

    /////////路径压缩：
    if(fa[x]==x)return x;
    else{
        int root=get_root(fa[x]);
        fa[x]=root;
        return root;
    } 
}*/

/////压压行
int get_root(int x){
    if(x==fa[x])return x;
    return fa[x]=get_root(fa[x]);
} 

int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;//一开始，所有点都是根，所有点的爸爸都是他自己 
    for(int i=1;i<=m;i++){
        int tp;cin>>tp;
        if(tp==1){
            int x,y;cin>>x>>y;
            int rootx=get_root(x);//找根（代表） 
            int rooty=get_root(y);
            //if(rootx==rooty)//啥也不用干 
            if(rootx!=rooty){
                fa[rootx]=rooty;
//              fa[rooty]=rootx;这么写也可以！代表的选取是任意的，所以连边的方向也是任意的 
            }
        }
        if(tp==2){//查询 
            int x,y;cin>>x>>y;
            int rootx=get_root(x);//找根（代表） 
            int rooty=get_root(y);
            if(rootx==rooty)puts("Y");//看看根（代表）是否是同一个人 
            else puts("N"); 
        }
    }
} 
//总复杂度:O(nlogn)

finish

ps:[启发式合并/按秩合并]与路径压缩结合复杂度可降低（dbwtql）
Tarjan告诉我们同时使用路径压缩和[按秩合并/启发式合并]，

此时复杂度可以做到O(nα(n))！ 其中α(n)是反阿克曼函数。它是一个增长非常缓慢的函数。对于任何一个有意义的数n，α(n)不会超过4.