什么是并查集？
并查集（Union-Find）是一种数据结构，主要用于处理动态连通性问题。它支持高效的合并（Union）和查询（Find）操作，常用于解决图的连通性、集合的合并等问题。
通过并查集，我们可以将两个（或多个）元素合并到一个集合中，并查询两个元素是否同属一个集合。
我们通过数组来实现这个操作
代码示范
指的是第i个元素的祖宗（可以理解为一个集合中的祖宗，代表这个集合）
一开始认为所有点都是孤立的一个集合，每个元素的祖宗就是它本身
1
2
3
4
| int fa[MAXN];
......
for(int i = 1; i <= n; i++)
fa[i] = i;
|
找祖宗的操作，如果一个节点的祖宗不是它本身,那么继续递归，直到一个元素的祖宗为自身（祖宗元素），返回集合的祖宗
1
2
3
4
5
| int find(int x)
{
if(fa[x] == x) return fa[x];
return find(fa[x]);
}
|
下面是合并操作，如果两个元素a、b不是同一个祖宗，那么将a的祖宗的直系父亲设为b
后续find(a)操作递归过程中会变为find(b)的找b祖宗的过程
1
2
3
4
5
6
7
8
9
| for(int i = 1 ;i <= m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
a = find(a);
b = find(b);
if(a!=b)
fa[a] = b;
}
|
当然你也可以把合并操作写到一个子函数里面
1
2
3
4
5
6
7
8
| void join(int a,int b)
{
int f1 = find(a);
int f2 = find(b);
if(f1!=f2) fa[f1] = f2;
}
......
join(a,b);
|
模板题
https://www.luogu.com.cn/problem/P1551
https://www.luogu.com.cn/problem/P3367
这是两道模板题，大家可以前往自己进行代码自测。
上述已经给出了合并与寻找的操作，这里只给出一个查询两元素是否同集合的伪代码
1
2
3
4
5
6
7
8
9
10
| for(int i = 1; i <= p; i++)
{
int a,b;
scanf("%d%d",&a,&b);
a = find(a);
b = find(b);
if(a == b)
printf("Yes\n");
else printf("No\n");
}
|
CF 970 (Div. 3) Problem D
题目来源：https://codeforces.com/contest/2008/problem/D
或者点击此处前往洛谷自测
题目描述
对于某个排列 ：
如果可以通过赋值 一定次数使 等于 ，则樱子称整数 可以从整数 到达。
例如，如果 ，那么，举例来说， 可以从 到达，因为
现在是 ，所以 可以从 到达。
排列中的每个数字都被染成黑色或白色。
樱子将函数 定义为从 可以到达的黑色整数的个数。
樱子对每个 的 都很感兴趣，但计算所有值变得非常困难，因此她请你作为她的好朋友来计算这个值。
长度为 的排列是由 个不同的整数组成的数组，这些整数从 到 按任意顺序排列。例如， 是一个排列，但 不是一个排列（数字 在数组中出现了两次）， 也不是一个排列（ ，但数组中包含 ）。
输入格式
第一行包含一个整数 ( ) — 测试用例数。
每个测试用例的第一行包含一个整数 ( ) — 测试用例中的元素个数。
每个测试用例的第二行包含 个整数 ( ) — 排列元素。
每个测试用例的第三行包含一个长度为 的字符串 ，由 ‘0’ 和 ‘1’ 组成。如果 ，那么数字 被涂成黑色；如果 ，那么数字 被涂成白色。
保证所有测试用例中 的总和不超过 。
输出格式
对于每个测试用例，输出 个整数 。
样例输入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 5
1
1
0
5
1 2 4 5 3
10101
5
5 4 1 3 2
10011
6
3 5 6 1 2 4
010000
6
1 2 3 4 5 6
100110
|
样例输出
1
2
3
4
5
| 1
0 1 1 1 1
2 2 2 2 2
4 1 4 4 1 4
0 1 1 0 0 1
|
思路：本题目实际上就是找到每个元素所在集合的元素的个数
我们令表示自然数序号,表示第个数的值
每次合并
我们定义一个数组is,表示第i个元素所在集合的黑色块的个数。 前提i为一个集合的祖宗
如果s[i] == 0,因为此时所有点还是孤立的
（一个点代表一个集合————for(int i = 1; i <= n; i++) fa[i] = i）
所以a[i+1]所在集合的黑色块个数为1（它本身）
1
2
3
4
5
6
7
8
| int is[200001];
......
cin>>s;
memset(is,0,sizeof(is));
for(int i = 1; i <= n; i++) cin>>a[i];
for(int i = 0; i < s.size(); i++)
if(s[i]=='0') is[a[i+1]] = 1;
|
下面进行合并集合的操作，如果两个数属于两个集合，那么合并后两个集合的黑色块个数相加
这里定义f2为合并后的祖宗节点，is[f2]代表合并后集合的黑色块总数
然后按照题意合并
1
2
3
4
5
6
7
8
9
10
11
12
| void join(int c1,int c2)
{
int f1 = find(c1),f2 = find(c2);
if(f1!=f2)
{
fa[f1] = f2;
is[f2] += is[f1];
}
}
......
for(int i = 1; i <= n; i++)
join(i,a[i]);
|
最后我们只需要输出每个点所在集合的黑色块个数，也就是找到它的祖宗——find(i)，然后is(find(i))即为所求
1
| for(int i = 1; i <= n; i++) cout<<is[find(i)]<<" ";
|
接下来给出整道题的全部代码
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
| #include<bits/stdc++.h>
using namespace std;
int fa[200001];
int is[200001];
int find(int x)
{
if(x==fa[x]) return x;
return fa[x] = find(fa[x]);
}
void join(int c1,int c2)
{
int f1 = find(c1),f2 = find(c2);
if(f1!=f2)
{
fa[f1] = f2;
is[f2] += is[f1];
}
}
int main(){
int t;
cin>>t;
while(t--)
{
memset(is,0,sizeof(is));
int n;
cin>>n;
string s;
int a[n+1];
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= n; i++) cin>>a[i];
cin>>s;
for(int i = 0; i < s.size(); i++)
if(s[i]=='0') is[a[i+1]] = 1;
for(int i = 1; i <= n; i++)
join(i,a[i]);
for(int i = 1; i <= n; i++) cout<<is[find(i)]<<" ";
cout<<endl;
}
return 0;
}
|
