并查集

基本概念

并查集是一种树形数据结构，用于处理不相交集合的合并（union）、查询（find）问题。

• find()：查找元素属于哪个集合，即根节点。
• union()：将两个集合合并为一个集合。

两个操作的时间复杂度近乎 $O(1)$。

并查集是树形数据结构，我们用数组模拟一颗树，通过数组下标来维护父子节点关系。下面来看一下并查集具体代码实现：

1. 并查集的存储
   使用一个数组 $fa$ 保存父节点（根节点的父节点就是自己）

int fa[SIZE];

2. 并查集的初始化
   设有 $n$ 个元素，起初所有的元素各自构成一个独立的集合，即有 $n$ 棵一个节点的树

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

3. 并查集的 find 操作
   对于每个单独的集合，我们把树根当作此集合的代表，若 x 是树根，则 x 就是集合代表；否则递归访问 fa[x] 直至根节点，在访问的过程中，还会更新 fa[x] 的值，这一步是并查集的关键优化，称为“路径压缩”。其完成的功能，可以理解为把一条路径上的每个点的父节点，都直接连到根节点上。

int find(int x) {
	if (x == fa[x]) return x;
	else return fa[x] = find(fa[x]); // 路径压缩
}

4. 并查集的 union 操作
   合并元素 x 和 元素 y 所在集合，等价于让 x 的树根作为 y 的树根的子节点。

void union(int x, int y) {
	fa[find(x)] = find(y); // 将x的根节点设为y的根节点的子节点
}

例题：合并集合

题目描述

一共有 $n$ 个数，编号是 $1\sim n$，最开始每个数各自在一个集合中。

现在要进行 $m$ 个操作，操作共有两种：

1. M a b，将编号为 $a$ 和 $b$ 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 $a$ 和 $b$ 的两个数是否在同一个集合中；

输入格式

第一行输入整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

数据范围：$1\le n,m\le {10}^5$

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 $a$ 和 $b$ 在同一集合内，则输出 Yes，否则输出 No。每个结果占一行。

输入样例

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例

Yes
No
Yes

题目分析

模板题

示例代码

#include <iostream>
using namespace std;

const int N = 100010;

int fa[N];

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

void uni(int x, int y) {
	fa[find(x)] = find(y);
} 

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) fa[i] = i;

    while (m -- ) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (op == 'M') uni(a, b);
        else {
            if (find(a) == find(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }

    return 0;
}

例题：连通块中点的数量

题目描述

给定一个包含 $n$ 个点（编号为 $1\sim n$）的无向图，初始时图中没有边。

现在要进行 $m$ 个操作，操作共有三种：

1. C a b，在点 $a$ 和点 $b$ 之间连一条边，$a$ 和 $b$ 可能相等；
2. Q1 a b，询问点 $a$ 和点 $b$ 是否在同一个连通块中，$a$ 和 $b$ 可能相等；
3. Q2 a，询问点 $a$ 所在连通块中点的数量；

输入格式

第一行输入整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

数据范围：$1\le n,m\le {10}^5$

输出格式

对于每个询问指令 Q1 a b，如果 $a$ 和 $b$ 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 $a$ 所在连通块中点的数量，每个结果占一行。

输入样例

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例

Yes
2
3

题目分析

操作1 和 操作2 与上一题没有任何区别，只要能解决 操作3，本题就可以顺利AC了，每个集合的代表元素（根节点）是否可以记录一些额外信息呢？我们可以开一个 SIZE 数组，用来保存每个集合的元素个数，对于某个元素 x，要查找 x 所在集合元素个数，只需要通过 SIZE[find(x)] 即可访问到。

那么如何维护 SIZE 数组呢？显而易见的是，在初始化并查集时，每个元素都是一个单独的集合，即所有 SIZE[i] 的初始值都是 $1$。

什么时候集合的 SIZE 会发生变化呢？当两个集合进行合并的时候！所以只需要当集合合并时，把根节点的 SIZE 加起来即可。

示例代码

#include <iostream>
using namespace std;

const int N = 100010;

int fa[N], SIZE[N];

int find(int x) {  // 返回x的根
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

void uni(int x, int y) {  // 合并x，y
	int rx = find(x), ry = find(y);
	fa[rx] = ry;
	SIZE[ry] += SIZE[rx];  // 合并的时候同时更新集合元素个数
} 

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        fa[i] = i;
        SIZE[i] = 1;
    }

    while (m -- ) {
        string op;
        cin >> op;
        if (op == "C") {
        	int a, b;
        	cin >> a >> b;
        	if (find(a) == find(b)) continue; // 避免自己与自己重复合并
        	uni(a, b);
		}
        else if (op == "Q1") {
            int a, b; cin >> a >> b;
            if (find(a) == find(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        else {
        	int a; cin >> a;
        	cout << SIZE[find(a)] << endl;
		}
    }
    return 0;
}