什么是并查集？

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

代码示范

$fa[i]$指的是第i个元素的祖宗（可以理解为一个集合中的祖宗，代表这个集合）
一开始认为所有点都是孤立的一个集合，每个元素的祖宗就是它本身

1 2	int fa[MAXN]; for (int i = 1; i <= n; i++) fa[i] = i;

找祖宗的操作，如果一个节点的祖宗不是它本身，那么继续递归，直到一个元素的祖宗为自身（祖宗元素），返回集合的祖宗

1	int find(int x) { return fa[x] == x ? x : find(fa[x]); }

下面是合并操作，如果两个元素a、b不是同一个祖宗，那么将a的祖宗的直系父亲设为b
后续find(a)操作递归过程中会变为find(b)的找b祖宗的过程

for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    a = find(a);
    b = find(b);
    if (a != b) fa[a] = b;
}

当然你也可以把合并操作写到一个子函数里面

void join(int a, int b) {
    int x = find(a), y = find(b);
    if (x != y) fa[x] = y;
}

join(a, b);

模板题

https://www.luogu.com.cn/problem/P1551
https://www.luogu.com.cn/problem/P3367
这是两道模板题，大家可以前往自己进行代码自测。
上述已经给出了合并与寻找的操作，这里只给出一个查询两元素是否同集合的伪代码

for (int i = 1; i <= p; i++) {
    int a, b;
    cin >> a >> b;
    a = find(a);
    b = find(b);
    cout << (a == b ? "Yes\n" : "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) $ 。

样例输入

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
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)$

我们定义一个数组 cnt，cnt[i] 表示以 i 为祖宗的集合中有多少个黑色点。最开始每个点都是一个独立集合，如果 **s[i] == ‘0’**，说明排列中的 a[i + 1] 是黑色的，因此把对应位置记为 $1$。

vector<int> cnt(n + 1);
for (int i = 0; i < n; i++) {
    if (s[i] == '0') cnt[a[i + 1]] = 1;
}

下面进行合并操作。如果两个点属于不同集合，就把其中一个祖宗接到另一个祖宗下面，并将两个集合的黑色点数量相加。

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

void join(int a, int b) {
    int x = find(a), y = find(b);
    if (x != y) {
        fa[x] = y;
        cnt[y] += cnt[x];
    }
}

for (int i = 1; i <= n; i++) join(i, a[i]);

最后只需要找到每个点的祖宗 **find(i)**，再输出祖宗所在集合记录的黑色点数量即可。

1	for (int i = 1; i <= n; i++) cout << cnt[find(i)] << " \n"[i == n];

接下来给出整道题的全部代码

#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

vector<int> fa, cnt;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void join(int a, int b) {
    int x = find(a), y = find(b);
    if (x != y) {
        fa[x] = y;
        cnt[y] += cnt[x];
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    fa.resize(n + 1);
    cnt.assign(n + 1, 0);
    iota(fa.begin(), fa.end(), 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') cnt[a[i + 1]] = 1;
    }
    for (int i = 1; i <= n; i++) join(i, a[i]);
    for (int i = 1; i <= n; i++) cout << cnt[find(i)] << " \n"[i == n];
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

总结与常见问题

常见问题

为什么要让 fa[i] = i？ 因为初始化时每个元素都自成一个集合，它的祖宗自然是自己。
为什么 find 里要写 fa[x] = find(fa[x])？ 这是路径压缩。查询结束后，沿途节点会直接连接到祖宗，后面的查询会快很多。
合并后为什么要把统计量累加到新祖宗？ 集合的信息应该由祖宗统一维护，否则查询到祖宗后无法得到完整答案。
并查集能不能维护集合内元素的顺序？ 不能。它擅长判断连通和合并集合，但不会保留集合内部的先后关系。

复杂度分析

初始化：时间复杂度 $O(n)$，空间复杂度 $O(n)$。
单次查询或合并：配合路径压缩后，均摊时间复杂度为 $O(\alpha(n))$，实际可以看作接近 $O(1)$。
本文例题：总时间复杂度 $O(n\alpha(n))$，空间复杂度 $O(n)$。