并查集 基础篇
概述
👉并查集 提高篇
定义：
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。
主要构成：
并查集主要由一个整型数组pre[ ]和两个函数find( )、join( )构成。
数组 pre[ ] 记录了每个点的前驱节点是谁，函数 find(x) 用于查找指定节点 x 属于哪个集合，函数 join(x,y) 用于合并两个节点 x 和 y 。
find函数
| int find(int x)
{
while(pre[x] != x) //如果x的上级不是自己
x = pre[x]; //x继续找他的上级
return x; //找到
}
|
join函数
| void join(int x,int y)
{
int fx=find(x), fy=find(y); // 找x的上级，y的上级
if(fx != fy) // 上级不相等，合并
pre[fx]=fy;
}
|
路径压缩
从find函数可以看出，从某个节点出发寻找根节点时，需要途径一系列的节点，而这些节点的上级都是同一个，因此可以在寻找的过程中将这些节点的上级都顺带修改了，简单说来就是将x到根节点路径上的所有点的pre（上级）都设为根节点。代码如下：
| int find(int x) //查找结点 x的根结点
{
if(pre[x] == x) return x; //递归出口：x的上级为 x本身，即 x为根结点
return pre[x] = find(pre[x]); // 修改途径节点的根节点
}
|
例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≤105\)
输入样例
| 4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
|
输出样例
题解
并查集模板题
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | #include<iostream>
using namespace std;
const int N = 100010 ;
int p[N] , n , m;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m ;
for(int i = 0 ; i <= n ; i ++) p[i] = i ;
while( m --)
{
char op;
int a, b ;
cin >>op >> a>> b;
if(op =='M') p[find(a)] = find(b);
else
{
if(find(a) == find(b)) cout <<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
}
|
例2.连通块中点的数量
题目链接
题目描述
给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；Q2 a，询问点 a 所在连通块中点的数量；
输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
\(1≤n,m≤105\)
输入样例
| 5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
|
输出样例
题解
C和Q1操作为并查集基本操作，Q2操作要求知道与a有相同根节点的节点所构成集合的大小，因此在每次join操作时更新集合大小即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 | #include<iostream>
using namespace std;
const int N = 100010;
int n , m ;
int p[N] ,psize[N]; // psize存集合大小
int find(int x )
{
if(p[x] != x ) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; i ++)
{
p[i] = i ;
psize[i] = 1;
}
while(m --)
{
string op;
int a , b;
cin>>op;
if(op =="C")
{
cin>>a>>b;
if(find(a) == find(b)) continue;
psize[find(b)] +=psize[find(a)];
p[find(a)] =find(b);
}
else if(op == "Q1")
{
cin >> a >> b;
if(find(a) == find(b)) cout << "Yes"<<endl;
else cout<< "No"<<endl;
}
else
{
cin>>a;
cout<<psize[find(a)]<<endl;
}
}
return 0;
}
|
例3.食物链
题目链接
题目描述
动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。
A 吃 B，B 吃 C，C 吃 A。
现有 N 个动物，以 1∼N 编号。
每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是 1 X Y，表示 X 和 Y 是同类。
第二种说法是 2 X Y，表示 X 吃 Y。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 X 或 Y 比 N 大，就是假话；
- 当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入格式
第一行是两个整数 N 和 K，以一个空格分隔。
以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。
若 D=1，则表示 X 和 Y 是同类。
若 D=2，则表示 X 吃 Y。
输出格式
只有一个整数，表示假话的数目。
数据范围
\(1≤N≤50000,\)
\(0≤K≤100000\)
输入样例
| 100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
|
输出样例
题解
解法1:若x和y已经确定关系，则x和y已经有了相同的根节点，因此我们可以通过维护x和y到根节点的距离来判断他们之间的关系，对3取余后距离取值为0，1，2，分别对应x和y同类，x吃y，y吃x三种状态，若根节点相同，判断距离，若不相同，则合并即可
解法2:扩展域并查集，开三倍空间，令1-n为同类域，n+1-2n为捕食域，2n+1-3n为天敌域，每次修改时同时维护三个域，例如x吃y，则在x的捕食域中加入y，在y的天敌域中加入x，同时在y的捕食域是捕食x的天敌域。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119 | // 解法1
#include <iostream>
using namespace std;
const int N = 50010;
int n, m;
int p[N], d[N];
int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int res = 0;
while (m -- )
{
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
if (x > n || y > n) res ++ ;
else
{
int px = find(x), py = find(y);
if (t == 1)
{
if (px == py && (d[x] - d[y]) % 3) res ++ ;
else if (px != py)
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else
{
if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
else if (px != py)
{
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}
printf("%d\n", res);
return 0;
}
// 解法2
//这里我们将三个域,分别转化为了n,n+n,n+n+n.因为读入方面特别烦.
#include <bits/stdc++.h>
using namespace std;
int fa[200000];
int n,m,k,x,y,ans;
int get(int x)
{
if(x==fa[x])
return x;
return fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
fa[get(x)]=get(y);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=3*n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&k,&x,&y);
if(x>n || y>n)
ans++;
else if(k==1)
{
if(get(x)==get(y+n) || get(x)==get(y+n+n)) //如果x,y是同类,但是x是y的捕食中的动物,或者x是y天敌中的动物,那么错误.
ans++;
else
{
merge(x,y);
merge(x+n,y+n);
merge(x+n+n,y+n+n);
}
}
else
{
if(x==y || get(x)==get(y) || get(x)==get(y+n)) //x就是y,或者他们是同类,再或者是y的同类中有x
ans++;//都是假话
else
{
merge(x,y+n+n);//y的天敌域加入x
merge(x+n,y);//x的捕食域加入y
merge(x+n+n,y+n);//x的天敌域是y的捕食域.
}
}
}
cout<<ans<<endl;
}
//x是同类域.
//x+n是捕食域
//x+n+n是天敌域
|