欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

详解并查集

程序员文章站 2022-06-24 08:11:23
详解并查集 Powered by WSY in SSF 2019-11-02 13:46 【1】并查集的定义: 并查集(Disjoint Set)是一种非常精巧的非常实用的数据结构,它主要用来处理一些不相交集合的合并问题,经典的例子有联通子图,最小生成树的克鲁斯-卡尔算法。 【2】并查集的经典问题: ......

                                                                                            详解并查集

                          powered by wsy in ssf

                                   2019-11-02  13:46

【1】并查集的定义:

  并查集(disjoint  set)是一种非常精巧的非常实用的数据结构,它主要用来处理一些不相交集合的合并问题,经典的例子有联通子图,最小生成树的克鲁斯-卡尔算法。


 

【2】并查集的经典问题:

  我们通常使用“帮派”、“团伙”等问题举例说明并查集。例如帮派问题:

  在某城市里住着n个人,任何两个认识的人不是朋友就是敌人,而且满足: 1、 我朋友的朋友是我的朋友; 2、 我敌人的敌人是我的朋友; 所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息,即某两个人是朋友,或者某两个人是敌人,请你编写一个程序,计算出这个城市最多可能有多少个团伙?

   这是一个非常经典的并查集问题,接下来就用这个问题的代码为您详解并查集。


 

【3】并查集问题的基本思路:

  第一步   初始化:

  我们需要对存储公共祖先的数组进行初始化,一般情况下,将该数组命名为s。

  首先,我们说 s[i] 是以节点 为元素的独立集合,在开始的时候不处理他和它的朋友之间的关系。

  然后,以元素的值表示他的集 s[i] 的值,例如 元素1的集 s[1]=1,如图1.1所示。

  详解并查集

  第二步   计算+合并:

  合并,例如加入第1个朋友关系(1,2),如图1.2所示,在并查集s中,把节点1合并到节点2。

  详解并查集

  之后,以此类推,直到合并成如图1.3的样子。

  详解并查集

  


 

  代码君:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1000+50;
 4 int r[maxn],enemry[maxn];
 5 int find(int x)
 6 {
 7     return (!r[x])?x:(find(r[x]));
 8 }
 9 void union(int a, int b) 
10 {
11     a=find(a); 
12     b=find(b);
13     if(a==b) return;  
14     if(a!=b) r[b]=a;
15 }
16 int main()
17 {
18     memset(r,0,sizeof(r));
19     memset(enemry,0,sizeof(enemry));
20     int m,n,x,y,j;
21     int ans=0;
22     char ch;
23     cin>>n>>m;
24     for(int i=0;i<m;i++)
25     {
26         cin>>ch>>x>>y;
27         if(ch=='0')
28         {
29             if(enemry[x]) union(y,enemry[x]);
30             else enemry[x]=y;
31             if(enemry[y]) union(x,enemry[y]);
32             else enemry[y]=x;
33         }
34         else union(x,y);
35     }
36     for(int i=1;i<=n;i++)
37     {   
38         j=find(i);
39         if(j==i) ans++;
40     }
41     cout<<ans<<endl;
42     return 0;
43 }//代码来源:https://blog.csdn.net/hyqsblog/article/details/45057877

 


 

【4】代码解读+详解

  再次感谢  https://blog.csdn.net/hyqsblog/article/details/45057877  提供的代码。

  从主函数开始。

  第18-19行,第1部分,初始化

  初始化r数组,enemry数组(这里很重要,在某些涉及到多组数据的题目时,初始化如果不写,会酿成大错)

  第20-23行,第2部分,基础定义+输入

  这里定义了一些基本的,后面需要使用的变量。

  之后还有一些基础的输入,包括n和m。

  第24-35行,第3部分,循环查找,实现并查集中的 “合并”

  循环,循环每组关系,查找。

  line 27:如果这组关系是 “敌对”,那么就使用union函数实现 “敌对合并” 的操作

  line 34:如果这组关系是 “友好”,那么就使用union函数实现 “友好合并” 的操作

  第9-15行,第4部分,实现合并

  使用find函数实现查找合并

  第5-8行,第5部分,实现查找

  全文只有一句话,但是能实现具体的返回判断,使用二元运算符

  


【5】并查集题目推荐:

poj2524 并查集简单题 ubiquitous religions
poj1611 并查集简单题 the suspects
poj1703 并查集简单题 find them, catch them
poj2236 并查集简单题 wireless network
poj2492 并查集中等题 a bug's life
hdu3635 并查集中等题 dragon balls
hdu1856 并查集难题 more is better
hdu1198 并查集传奇 farm irrigation