【算法基础3】并查集

并查集

现在我们要完成两个操作：
1.将两个集合合并
2.询问两个元素是否在一个集合当中
这两个操作的时间复杂度均为O(n)，但我们使用并查集的话，可以在近乎O(1)的时间内完成这一操作。
基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号。每个节点存储它的父节点。用p[x]来表示x的父节点。
于是并查集就转换为了3个基本问题：
1.如何判断树根？ if(p[x]==x)
2.如何求x在哪个集合内？ while(p[x]!=x) x=p[x];
3.如何合并两个集合？把一个集合的树直接插入到另一个树的树根上。如p[x]是x的集合编号，p[y]是y的集合编号，那就令p[x]=y;
此时我们发现，最重要的查询操作的时间复杂度仍然不够理想，我们仍然需要遍历很多次，这是我们就要对并查集操作进行优化。
最常用的优化叫路径压缩，就是在向上查找到根节点之后，把路径上的所有的节点的p[x]都指向根节点，此后如果再查询集合编号，就无需多次查询，直接指向了根节点。
在路径压缩优化之后，并查集查询集合的时间复杂度就趋近于O(1)了。

模版题

AcWing836. 合并集合

#include <iostream>

using namespace std;

const int N=1e6+10;

int n,m;
int p[N];

//返回x的祖宗节点+路径压缩
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);//x如果不是根节点，就继续向上查找
    return p[x];
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;

    for(int i=1;i<=n;i++) p[i]=i;//初始情况下节点离散，根节点就是自己

    while(m--){
        char op[2];
        int a,b;
        cin>>op>>a>>b;

        if(op[0]=='M') p[find(a)]=find(b);
        else{
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

例题1

AcWing837. 连通块中点的数量

#include <iostream>

using namespace std;

const int N=1e6+10;

int n,m;
int p[N],siz[N];//size记录每个点所在集合的元素个数

//返回x的祖宗节点
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);//x如果不是根节点，就继续向上查找
    return p[x];
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++){
        p[i]=i;//初始情况下节点离散，根节点就是自己
        siz[i]=1;//集合内只有自己
    }
    while(m--){
        string op;
        int a,b;
        cin>>op;

        if(op=="C"){
            cin>>a>>b;
            if(find(a)!=find(b)){
                siz[find(b)]+=siz[find(a)];//※参见注释
                p[find(a)]=find(b);
            }
        }
        else if(op=="Q1"){
            cin>>a>>b;
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }
        else{
            cin>>a;
            cout<<siz[find(a)]<<endl;
        }
    }
    
    return 0;
}

※连通块大小的加和需要在操作集合之前，否则先操作集合会使连通块大小改变。要避免这一问题，可以选择先将两个集合的大小取出来再做这些操作，如：

if(op=="C")
        {
            cin>>a>>b;
            a=find(a),b=find(b);
            if(a!=b)
            {
                p[a]=b;
                siz[b]+=siz[a];
            }
        }

此外，数组起名为size[]可能会与C++的关键字冲突，故这里命名为siz。