详解并查集
详解并查集
powered by wsy in ssf
2019-11-02 13:46
【1】并查集的定义：
并查集（disjoint set）是一种非常精巧的非常实用的数据结构，它主要用来处理一些不相交集合的合并问题，经典的例子有联通子图，最小生成树的克鲁斯-卡尔算法。
【2】并查集的经典问题：
我们通常使用“帮派”、“团伙”等问题举例说明并查集。例如帮派问题：
在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、 我朋友的朋友是我的朋友； 2、 我敌人的敌人是我的朋友； 所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？
这是一个非常经典的并查集问题，接下来就用这个问题的代码为您详解并查集。
【3】并查集问题的基本思路：
第一步 初始化：
我们需要对存储公共祖先的数组进行初始化，一般情况下，将该数组命名为s。
首先，我们说 s[i] 是以节点 i 为元素的独立集合，在开始的时候不处理他和它的朋友之间的关系。
然后，以元素 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 |