C/C++并查集的查询与合并实现原理

时间:2023-03-20 Ggggggtm 人气:0

标题：并查集的查询与合并详解作者：@Ggggggtm 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景

一、并查集的概念

并查集是一种树形的数据结构。使用树型结构来存储数据。树根的编号即为整个树的标号，且每个节点存储的数据是他的父节点下标。

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

二、并查集的实现

1.并查集不同集合(树)的形成

我们把并查集不同集合（树）的实现主要分为以下几个点：

我们先给出n个数据，把n个数据存储到不同的集合当中（p[ i ] = i），在这里我们把每个p[ i ]分别看成一个不同集合（也就是一棵树）。
p[ i ] = i，i即为这棵树的编号，这颗树下面的孩子节点存储的数据是父节点的下标。
当p[ i]=i 时，就相当于找到了根节点。
我们刚开始每个集合中的元素只有一个。后续合并后，集合元素个数不断增加。

2.find()函数找一个元素集合的编号

（元素所属于树的祖宗）

我们查找一个元素的集合，把元素的当作下标传给find()函数，代码如下：

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

我们p[x]中存储的正是他的父节点，从而就可以一直往上查找，直到p[ x ]=x时结束。当p[ x ]=x时，就相当于找到了根节点。此时的p[ x ]存储的是这棵树的编号。我这发现，刚开始每个集合当中都只有一个元素，也就是p[ x ]，后面我们会对不同的集合进行合并，使得一个集合有多个元素。

我们再找祖宗节点时进行了路径压缩。什么是路径压缩呢？路径压缩就是我们在查找某个元素的祖宗时，在找父节点的这条路经上的元素都指向祖宗节点，以便于我们后面的查找的时间复杂度近乎O（1）。

3.合并两个不同集合(合并两棵不同的树)

我们直到了每棵树的根节点存储的是这个树的编号，而不是父节点。当我们要合并两颗树时，我们只需要把一棵树的根节点存储的编号改为另一棵树的根节点编号。简单的理解就是一个树的根节不再是根节点，而是一个子节点，该树的根节点存储的也不再是编号，而是存储的父节点，该父节点就是另一棵树的根节点。我们看代码：

//合并  把a的祖宗节点的父节点当作b的祖宗结点
p[find(a)]=find(b);

4.查询两个元素是否在一个集合

我们有了find（）函数，就可以很简单的判断出两个元素的是否在同一个集合当中（两个元素是否在同一个树中）。我们只需要判断两个元素集合的编号是否相同（两个元素的祖宗节点是否相同）即可。我们看代码：

//看a、b两个元素是否在同一个集合当中
if(find(a)==find(b))
    cout<<"Yes"<<endl;
else
    cout<<"No"<<endl;

5.并查集例题训练1

一共有 n 个数，编号是1∼n，最开始每个数各自在一个集合中。

现在要进行m个操作，操作共有两种：

M a b，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为a和b的两个数是否在同一个集合中；

输入格式：

第一行输入整数n和m。

接下来m行，每行包含一个操作指令，指令为M a b或Q a b中的一种。

输出格式：

对于每个询问指令Q a b，都要输出一个结果，如果a和b在同一集合内，则输出Yes，否则输出No。

每个结果占一行。

数据范围：

1≤n,m≤10e5 1≤n,m≤10e5

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

答案如下：

#include<iostream>
using namespace std;
const int N=100010;
int p[N];
//找祖宗+路径压缩
int find(int x)
{
    if(p[x]!=x)
    {
        p[x]=find(p[x]);
    }
    return p[x];
}
int main()
{
    int n,m;
    scanf("%d%d",&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')
        {
            //合并  把a的祖宗节点的父节点当作b的祖宗结点
            p[find(a)]=find(b);
        }
        else
        {
            if(find(a)==find(b))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }
    return 0;
}

6.并查集例题训练2

给定一个包含nn个点（编号为1∼n1∼n）的无向图，初始时图中没有边。

现在要进行mm个操作，操作共有三种：

C a b，在点aa和点bb之间连一条边，aa和bb可能相等；
Q1 a b，询问点aa和点bb是否在同一个连通块中，aa和bb可能相等；
Q2 a，询问点aa所在连通块中点的数量；

输入格式

第一行输入整数nn和mm。

接下来mm行，每行包含一个操作指令，指令为C a b，Q1 a b或Q2 a中的一种。

输出格式

对于每个询问指令Q1 a b，如果aa和bb在同一个连通块中，则输出Yes，否则输出No。

对于每个询问指令Q2 a，输出一个整数表示点aa所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

我们这个题相对于上个题就是对出了一个统计一个集合元素的个数。整体思路大同小异，我们直接看代码解析：

#include<iostream>
using namespace std;
const int N=100010;
int p[N],cnt[N];
int find(int x)
{
    if(p[x]!=x)
    {
        p[x]=find(p[x]);
    }
    return p[x];
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        p[i]=i;
        cnt[i]=1;
    }
    while(m--)
    {
        char op[5];
        int a,b;
        scanf("%s",op);
        if(op[0]=='C')
        {
            scanf("%d%d",&a,&b);
            if(find(a)==find(b))
                continue;
            cnt[find(b)]+=cnt[find(a)];
            p[find(a)]=find(b);
        }
        else if(op[1]=='1')
        {
            scanf("%d%d",&a,&b);
            if(find(a)==find(b))
                printf("Yes\n");
            else
                printf("No\n");
        }
        else
        {
            scanf("%d",&a);
            printf("%d\n",cnt[find(a)]);
        }
    }
    return 0;
}

注意，我们刚开始每个集合中的元素只有一个。后续合并后，集合元素个数不断增加。

三、总结

我们主要掌握find（）函数，并查集算法中，最为核心的就是find（）函数。在这个算法中，路径压缩给我们的算法效率提高了很多，这个也是需要理解的。合并、查询是并查集的两个主要操作，我们也应该熟悉理解。

加载全部内容