---
title: "并查集"
description: "维护不相交集合，支持快速合并与查询连通性。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 并查集

有一类问题反复出现：不断把两个元素归成一类，同时问两个元素是不是同一类。朋友的朋友也是朋友、两个城市通不通路、两个点连不连通，都是这个形式。

并查集（Disjoint Set Union，DSU）专门解决这类问题。它只支持两个操作，但都做到了几乎 $O(1)$。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

| 考试 | 大纲要求 | 本章位置 |
| --- | --- | --- |
| CSP-J/S 提高级 | 2.3.2 集合与森林：并查集 | 全章 |

## 基本思路

并查集把元素分成若干个不相交的集合。每个集合选一个**代表元**，用一个数组记下每个元素的「上级」：

```cpp
int fa[100005]; // fa[i] 表示 i 的父节点

- 如果 `fa[i] == i`，说明 i 是自己这个集合的代表元，也就是根。
- 否则沿着 `fa` 一直往上找，一直找到根为止。

两个元素属于同一个集合，当且仅当它们的根相同。

初始时每个元素各成一个集合，`fa[i] = i`。

```cpp
void init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i;
}

## 查找与路径压缩

`find(x)` 要找 x 所在集合的根。

```cpp
int find(int x) {
    if (fa[x] == x) return x;       // 自己是根
    return fa[x] = find(fa[x]);     // 递归找根，顺便把沿途节点直接挂到根上
}

关键是 `return fa[x] = find(fa[x])` 这一句。它不仅找到了根，还把 x 的父节点直接改成根。这个操作叫**路径压缩**。

为什么重要？如果只是老老实实沿链往上找，树可能退化成一条链，每次查找都是 $O(n)$。路径压缩之后，第一次找要走的路径，之后几乎所有节点都直接连着根，后续查找接近 $O(1)$。

## 合并

把两个集合合并，只需要把其中一个的根接到另一个的根上。

```cpp
void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;   // 已经在一起了
    fa[rx] = ry;            // 把 rx 的树接到 ry 上
}

这样写虽然简单，但如果总是把大树接到小树上，树会越接越高。加一条**按大小合并**（或按秩合并）的规则就能避免：

```cpp
int sz[100005]; // sz[i] 只在 i 是根时有意义，表示集合大小

void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        sz[i] = 1;
    }
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (sz[rx] < sz[ry]) swap(rx, ry); // 让 rx 是较大的那个
    fa[ry] = rx;                       // 小的接到大的上
    sz[rx] += sz[ry];
}

路径压缩和按大小合并一起用，单次操作的均摊复杂度是 $O(\alpha(n))$，其中 $\alpha$ 是反阿克曼函数。这个函数增长极慢，在实际数据规模下不会超过 5，所以可以直接当作 $O(1)$。

## 典型应用

### 判断连通性

给你一些「A 和 B 是朋友」的关系，问 C 和 D 是不是朋友。

```cpp
for (每个关系 a b) unite(a, b);
if (find(c) == find(d)) cout << "是" << endl;
else cout << "不是" << endl;

### 统计连通块个数

合并完所有关系后，数一数有多少个节点满足 `find(i) == i`。

```cpp
int cnt = 0;
for (int i = 1; i <= n; i++) {
    if (find(i) == i) cnt++;
}
cout << cnt << endl;

### 判断无向图是否有环

遍历每一条边，如果两个端点已经在同一个集合里，说明这条边会成环。

```cpp
bool hasCycle = false;
for (每条边 u v) {
    if (find(u) == find(v)) hasCycle = true;
    else unite(u, v);
}

### Kruskal 最小生成树

Kruskal 算法的核心就是并查集：按边权从小到大排序，依次尝试加入每条边，如果两个端点不连通就加入，否则跳过。判断连通性靠的就是 `find`。

### 带权并查集

有时除了「是否同类」，还要维护两个元素之间的相对关系，比如「比对方多多少」。这时给 `fa` 配上另一个数组记录到父节点的权值，`find` 时顺便把权值累加，叫带权并查集。属于提高级内容，遇到具体题目再学。

## 复杂度

| 实现方式 | 单次操作 |
| --- | --- |
| 朴素 | $O(n)$ |
| 只有路径压缩 | 均摊 $O(\log n)$ |
| 只有按秩合并 | $O(\log n)$ |
| 两者都用 | 均摊 $O(\alpha(n))$，实际可视为 $O(1)$ |

## 常见易错点

- 忘记初始化 `fa[i] = i`，`find` 会跑到奇怪的地方。
- 合并时写 `fa[x] = y`，直接接了两个具体节点。必须接两个**根**：`fa[find(x)] = find(y)`。
- 路径压缩写成了 `find(fa[x])` 但没有赋值回去，压缩就失效了。
- 用 `sz` 数组时只在根节点上维护，合并后旧根的 `sz` 就不再有意义。
- 递归版 `find` 在链特别长时可能爆栈，可以改成循环。
- 并查集只能合并，不能拆分。要支持删除就得用别的结构。
- **合并时忘了路径压缩**。`fa[a] = b` 里的 `a`、`b` 必须是 `find` 的结果，直接写 `fa[u] = v` 会挂错层级。
- **判环时先合并再判断**。必须先判断 `find(u) == find(v)`，再决定是否合并；顺序反了就永远判不出环。
- **用并查集判有向图的环**。并查集只适用于无向图，有向图要用拓扑排序或 DFS 状态标记。
- **统计连通块时重复调用 `find`**。边合并边用 `cnt--` 维护更快，也能避免漏改。

## 练习

### 练习 1：连通图（最少加几条边）

在线评测练习：[P1110 连通图](https://dailyup.run/tasks/194)

> GESP C++ 2025.09 · 七级题 1

#### 题目描述

给定一张包含 $n$ 个结点与 $m$ 条边的无向图。如果从一个结点经过若干条边可以到达另一个结点，则称这两个结点是连通的。

你需要向图中加入若干条边，使得图中任意两个结点都是连通的。求最少需要加入的边的条数。

注意给出的图中可能包含重边与自环。

#### 输入格式

第一行两个正整数 $n$、$m$。接下来 $m$ 行，每行两个正整数 $u_i$、$v_i$。

#### 输出格式

输出一行一个整数，表示最少需要加入的边的数量。

#### 输入输出样例

输入

```
4 4
1 2
2 3
3 1
1 4

输出

```
0

输入

```
6 4
1 2
2 3
3 1
6 5

输出

```
2

#### 数据范围

- $1 \le n \le 10^5$，$1 \le m \le 10^5$。

#### 题目分析

**这道题把并查集的「数连通块」用到了极致**，而且比 DFS/BFS 更简洁——**不需要建图**，边读边合并就行。

**核心结论**：把 $s$ 个连通块连成一整块，最少需要 $s - 1$ 条边。

为什么？把每个连通块压成一个大点，现在有 $s$ 个大点、0 条边，要让它们连通至少需要 $s - 1$ 条边（生成树）；而 $s - 1$ 条边也够了——每加一条边就能合并两个连通块。

**所以算法就是三步**：

1. 初始化 `fa[i] = i`，用 `cnt = n` 记录「当前连通块个数」；
2. 每读入一条边 $(u, v)$，如果 `find(u) != find(v)`，就合并并把 `cnt--`；
3. 最后输出 `cnt - 1`。

**几个值得注意的地方：**

1. **不需要存图**。并查集边读边合并，空间只要 $O(n)$。而 DFS/BFS 要建邻接表，空间 $O(n + m)$。这是并查集在这类「只问连通性」题目上的优势。
2. **重边与自环自动被忽略**。自环 $(u, u)$ 时 `find(u) == find(u)`，不合并；重边第二次读到时已经连通，也不合并。**不需要写任何特判**。
3. **`cnt` 的维护方式**。也可以用「最后统计 `find(i) == i` 的个数」，但边合并边减更快，而且避免了对每个点再调一次 `find`。
4. **$n = 1$**：`cnt = 1`，输出 0，正确。
5. **$m = 0$**：`cnt = n`，输出 $n - 1$，正确。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/unionfind/index.md

### 练习 2：无向图判环

#### 题目描述

给定一张 $n$ 个顶点、$m$ 条边的无向图（无自环、无重边），判断它是否包含环。

#### 输入格式

第一行两个整数 $n$、$m$；接下来 $m$ 行，每行两个整数 $u$、$v$。

#### 输出格式

包含环输出 `YES`，否则输出 `NO`。

#### 输入输出样例

输入

```
4 3
1 2
2 3
3 1

输出

```
YES

输入

```
4 3
1 2
2 3
3 4

输出

```
NO

#### 数据范围

- $1 \le n, m \le 10^5$。

#### 题目分析

这是并查集判环的标准写法，**比 DFS 版本更短，而且不需要建图、不需要记录父节点**。

**判据极其简洁**：按顺序处理每条边 $(u, v)$——

- 如果 `find(u) != find(v)`：两点还不连通，这条边是「有用的」，合并它们；
- 如果 `find(u) == find(v)`：**两点已经连通了，再加这条边必然成环**。

**为什么这个判据一定对？** 因为无向图的每条边连接两个点。如果它们已经在同一棵「合并树」里，说明之前已经有一条路径连通它们，这条新边就与那条路径构成一个环。

**和 DFS 版本的对比**（见「搜索算法」章节的练习）：

| 做法 | 是否需要建图 | 是否需要记父节点 | 代码长度 |
| --- | --- | --- | --- |
| DFS | 需要邻接表 | 需要传 `parent` 排除回头边 | 较长 |
| 并查集 | **不需要** | **不需要** | 极短 |

**但两者有一个重要区别**：并查集判环**只能判「有没有环」**，判不了「环在哪里」；而且**只能用于无向图**（有向图判环要用拓扑排序或 DFS 的「在栈中」标记）。

**题目特意说「无自环、无重边」**，是为了避免歧义——如果有自环 $(u,u)$，按上面的逻辑会立刻判定成环（`find(u)==find(u)`），这也符合直觉；有重边时两条相同的边也会构成一个 2-元环。**所以这个判据在有自环/重边时同样成立，只是题目想让你专注于一般情形。**

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/unionfind/index.md

> 顺带记住一个简单结论：**连通的无向图无环 ⟺ $m = n - 1$**（这样的图就是树）。所以如果题目保证图连通，直接用边数和点数比较就能判，连并查集都省了。

## 小结

- 并查集维护不相交集合，用 `find` 找代表元，用 `unite` 合并两个集合。
- 路径压缩把查找路径上的节点直接挂到根上，按大小合并保证树不会太深。
- 两者结合后单次操作是 $O(\alpha(n))$，可以当成常数。
- 典型应用是判连通、数连通块、判环和 Kruskal 最小生成树。
- $s$ 个连通块连成一整块，最少需要 $s - 1$ 条边。
- 并查集判无向图有环：处理每条边时，若两端已连通（`find(u) == find(v)`）就说明成环。
- 只问连通性时并查集比 DFS/BFS 更优：**不用建图**，边读边合并，空间只要 $O(n)$。

Source: https://cppguide.xyz/ds/unionfind/index.mdx
