c++中并查集的实现

何谓并查集

并查集实际上就是并集和查集的过程。那么什么是集呢？你可以把他近似地理解为一棵树。即一个根结点连着无数个子节点。

并查集的实现

给出例题：例题源网站（洛谷）
这里附：
题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入输出格式

输入格式：
第一行包含两个整数N、M，表示共有N个元素和M个操作。

接下来M行，每行包含三个整数Zi、Xi、Yi

当Zi=1时，将Xi与Yi所在的集合合并

当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N

输出格式：
如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N

输入输出样例

输入样例#1： 复制
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出样例#1： 复制
N
Y
N
Y
这就是最最基础的并查集模版了

初始化

我们会用到一个father数组，记录每一个节点的根结点
最初要把每一个节点都当作一个集，即

    father[i]=i;

这里我们需要用一个循环来实现，完整代码如下

    for(int i=1;i<=n;/*n即n个元素*/i++)
        father[i]=i;

然后初始化就完成啦。。

函数

并查集一定会用到一个getfather函数（其实名字你随便起）
这个函数就是去找根节点

int @H_406_106@getfather(int x)//找x的根结点
{//这其实是一个递归函数
    if(father[x]==x)//边界条件，如果x的根结点就是x（也就是说它没有更上边的祖宗了）
        return x;//就会返回x的值
    else
    {
        father[x]=getfather(father[x]); //不然的话就会一级一级找上去（先找到它爸爸，在找到它爸爸的爸爸，再找到它爸爸的爸爸的爸爸。。。。。）
    }
    return father[x];
}

读入

先上代码吧。。毕竟没什么难度

for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&amp;z[i],&x[i],&y[i]);
        z1[i]=getfather(x[i]);//z1数组用于存储每一个x[i]的根结点
        z2[i]=getfather(y[i]);//z2数组用于存储每一个y[i]的根结点
    }

并集

目的就是让一个集合的根结点成为另一个集合的根结点，这样这两个集合就有同一个根结点，就起到了合并的作用。（比如说小明的爷爷也是小李的爷爷，他俩就是亲戚）
代码如下

if(z[i]==1)
    {
        if (z1[i]!=z2[i])
            Union(z1[i],z2[i]);
    }

这个Union是我自己写的一个函数，它长这样：

void Union(int xx,int yy)
{
    int F1=getfather(xx);//f1就是 xx的根结点
    int f2=getfather(yy);//f2就是yy的根结点
    father[f1]=f2;//让xx的根结点成为yy的根结点（上面有解释）
    return;
}

由于这是一个void函数，所以你也可以直接把代码 粘出来。

查集

鉴于我们已经做过并集的工作，查集就变得轻松了很多，我们只需要确认两个点是否有 同一个根结点就行了，代码如下：

if(z[i]==2)
    {
        if(getfather(x[i])==getfather(y[i]))//如果 x[i]的根结点就是y[i]的根结点
        {
            cout<<"Y"<<endl;//就输出y
        }
        else
        {
            cout<<"N"<<endl;//不然就输出 n
        }
    }

应该不难懂吧？

本题完整代码如下

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,father[200000];
int z[200000],y[200000],x[200000];
int getfather(int x)
{
    if(father[x]==x)
        return x;
    else
    {
        father[x]=getfather(father[x]); 
    }
    return father[x];
}
void Union(int xx,int yy)
{
    int f1=getfather(xx);
    int f2=getfather(yy);
    father[f1]=f2;
    return;
}
int main()
{
    int z1[200000],z2[200000];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&z[i],&x[i],&y[i]);
        z1[i]=getfather(x[i]);
        z2[i]=getfather(y[i]);
    }
    for(int i=1;i<=m;i++)
    {
        if(z[i]==1)
        {
            if (z1[i]!=z2[i])
                Union(z1[i],z2[i]);
        }
        if(z[i]==2)
        {
            if(getfather(x[i])==getfather(y[i]))
            {
                cout<<"Y"<<endl;
            }
            else
            {
                cout<<"N"<<endl;
            }
        }
    }
    return 0;
}

还是建议自己去写一遍。
这里还有几道题
极其类似模版的题
局域网
营救
不会的可以自己去看一下题解。

tks