什么是并查集？

并查集（Union-Find）是一种数据结构，主要用于处理动态连通性问题。它支持高效的合并（Union）和查询（Find）操作，常用于解决图的连通性、集合的合并等问题。
通过并查集，我们可以将两个（或多个）元素合并到一个集合中，并查询两个元素是否同属一个集合。
我们通过数组来实现这个操作

代码示范

$fa[i]$指的是第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
或者点击此处前往洛谷自测

题目描述

对于某个排列 $ p $：

如果可以通过赋值 $ i=p_i $ 一定次数使 $ i $ 等于 $ j $，则樱子称整数 $ j $ 可以从整数 $ i $ 到达。
例如，如果 $ p=[3,5,6,1,2,4]$，那么，举例来说，$ 4 $ 可以从 $ 1 $ 到达，因为$$i = 1 \rightarrow i = p_1 = 3 \rightarrow i = p_3= 6 \rightarrow i = p_6 = 4$$

现在是 $ i=4$，所以 $ 4 $ 可以从 $ 1 $ 到达。

排列中的每个数字都被染成黑色或白色。

樱子将函数 $ F(i) $ 定义为从 $ i $ 可以到达的黑色整数的个数。

樱子对每个 $ 1 \leq i \leq n $ 的 $ F(i) $ 都很感兴趣，但计算所有值变得非常困难，因此她请你作为她的好朋友来计算这个值。

长度为 $ n $ 的排列是由 $ n $ 个不同的整数组成的数组，这些整数从 $ 1 $ 到 $ n $ 按任意顺序排列。例如， $ [2,3,1,5,4] $ 是一个排列，但 $ [1,2,2] $ 不是一个排列（数字 $ 2 $ 在数组中出现了两次）， $ [1,3,4] $ 也不是一个排列（ $ n=3 $ ，但数组中包含 $ 4 $）。

输入格式

第一行包含一个整数 $ t $ ( $ 1 \leq t \leq 10^4 $ ) — 测试用例数。

每个测试用例的第一行包含一个整数 $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — 测试用例中的元素个数。

每个测试用例的第二行包含 $ n $ 个整数 $ p_1, p_2, \dots, p_n $ ( $ 1 \leq p_i \leq n $ ) — 排列元素。

每个测试用例的第三行包含一个长度为 $ n $ 的字符串 $ s $，由 ‘0’ 和 ‘1’ 组成。如果 $ s_i = 0 $，那么数字 $ p_i $ 被涂成黑色；如果 $ s_i = 1 $，那么数字 $ p_i $ 被涂成白色。

保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $ 。

输出格式

对于每个测试用例，输出 $ n $ 个整数 $ F(1), F(2), \dots, F(n) $ 。

样例输入

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

思路：本题目实际上就是找到每个元素所在集合的元素的个数
我们令$i$表示自然数序号：$a_i$表示第$i$个数的值
每次合并$(i,a_i)$

我们定义一个数组is,$is[i]$表示第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)); //is默认都为0
      for(int i = 1; i <= n; i++) cin>>a[i];
for(int i = 0; i < s.size(); i++) //string索引从0开始
	if(s[i]=='0') is[a[i+1]] = 1; //针对string索引从0开始，数组从1开始，数组索引加1
      //因为输入的是a[i],所以令is[a[i+1]] = 1

下面进行合并集合的操作，如果两个数$c1、c2$属于两个集合，那么合并后两个集合的黑色块个数相加
这里定义f2为合并后的祖宗节点，is[f2]代表合并后集合的黑色块总数

然后按照题意合并$(i,a_i)$

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;
}