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

萌晓许 · 发布于 2023-4-19 16:23:19

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

一、并查集的概念

并查集是一种树形的数据构造。使用树型构造来存储数据。树根的编号即为整个树的标号，且每个节点存储的数据是他的父节点下标。
并查集被很多OIer认为是最简洁而优雅的数据构造之一，主要用于处置一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

二、并查集的实现

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

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

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个操作，操作共有两种：

输入格式：
第一行输入整数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;
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;
      cnt=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（）函数。在这个算法中，途径压缩给我们的算法效率进步了很多，这个也是需要理解的。合并、查询是并查集的两个主要操作，我们也应该熟悉理解。
到此这篇关于C/C++并查集的查询与合并实现原理的文章就介绍到这了,更多相关C++并查集内容请搜索网站以前的文章或继续阅读下面的相关文章希望大家以后多多支持网站！