408

数据结构

DS-04-07 并查集

---

一、定位信息

项目	内容
圈层	核心层（大纲考点）
前置知识	树的基本概念、数组存储、递归思想
知识网络定位	并查集是一种树形数据结构，用于处理不相交集合的合并与查询问题，是图论中判断连通性的基础工具
考点热度	M级（中频常考）：近5年出现约2-3次，常以选择题或算法设计题形式考查

---

二、知识点讲解

2.1 并查集的概念

并查集（Union-Find Set） 是一种用于管理元素所属集合的数据结构，支持两种基本操作：

1. 查找（Find）：确定某个元素属于哪个子集
2. 合并（Union）：将两个子集合并为一个集合

应用场景：

• 判断图中两个顶点是否连通
• 求图的连通分量个数
• Kruskal 最小生成树算法中的环检测

2.2 存储结构

并查集用树的双亲表示法（数组）存储。每个集合用一棵树表示，树中每个节点只存储其父节点的下标。

#define MAXSIZE 100
int parent[MAXSIZE];  // parent[i] 表示节点 i 的父节点下标
                       // 根节点的 parent 值为 -1（或负数表示集合大小）

初始化：每个元素自成一个集合，即每棵树只有根节点。

void Init(int S[], int n) {
    for (int i = 0; i < n; i++) {
        S[i] = -1;    // -1 表示根节点，同时可表示集合大小的相反数
    }
}

2.3 查找操作（Find）

朴素查找：从给定节点沿 parent 指针向上追溯，直到找到根节点（parent 为负数的节点）。

// 查找元素 x 所属集合的根
// 参数 S：并查集数组，x：待查找元素
// 返回值：x 所在集合的根节点下标
int Find(int S[], int x) {
    while (S[x] >= 0) {    // 当 x 不是根节点时
        x = S[x];          // 沿父指针向上追溯
    }
    return x;              // 返回根节点
}

时间复杂度：$O(h)$，其中 $h$ 是树高。最坏情况 $O(n)$。

路径压缩优化：在查找过程中，将路径上的所有节点直接挂到根节点下，降低后续查找的树高。

// 带路径压缩的查找
int Find_Compress(int S[], int x) {
    int root = x;
    while (S[root] >= 0) {  // 第一步：找到根
        root = S[root];
    }
    while (x != root) {     // 第二步：路径压缩
        int temp = S[x];    // 保存父节点
        S[x] = root;        // 将当前节点直接挂到根下
        x = temp;           // 继续处理原路径上的下一个节点
    }
    return root;
}

递归版路径压缩（更简洁但有栈开销）：

int Find_Recursive(int S[], int x) {
    if (S[x] < 0) return x;        // x 是根
    S[x] = Find_Recursive(S, S[x]); // 递归查找并压缩
    return S[x];
}

2.4 合并操作（Union）

朴素合并：将一棵树的根指向另一棵树的根。

// 合并两个元素所在的集合
void Union(int S[], int x, int y) {
    int rootX = Find(S, x);    // 找 x 的根
    int rootY = Find(S, y);    // 找 y 的根
    if (rootX != rootY) {      // 不在同一集合才合并
        S[rootX] = rootY;     // 将 rootX 挂到 rootY 下
    }
}

按秩合并优化：将较矮的树合并到较高的树下，避免树过高。

// 按秩（树高/集合大小）合并
// S[root] 存储的是集合大小的相反数（-size）
void Union_BySize(int S[], int x, int y) {
    int rootX = Find(S, x);
    int rootY = Find(S, y);
    if (rootX != rootY) {
        if (S[rootX] > S[rootY]) {  // rootX 的集合更小（负数比较）
            S[rootY] += S[rootX];   // 更新 rootY 的集合大小
            S[rootX] = rootY;       // 小树挂到大树下
        } else {
            S[rootX] += S[rootY];
            S[rootY] = rootX;
        }
    }
}

注意：S[root] 存储的是集合大小的相反数（负数），所以 S[root] 越小（绝对值越大），集合越大。

2.5 并查集的树形表示示例

初始状态（5个元素，各自为集合）：
parent: [-1, -1, -1, -1, -1]
下标：    0   1   2   3   4

执行 Union(0, 1)、Union(2, 3)、Union(3, 4)、Union(1, 3) 后：

parent: [-1,  0, -1,  2,  3]  → 经过路径压缩后 → [-1,  0, -1,  2,  2]

树形结构：
  0        2
  |       / \
  1      3   4

合并后（Union(1,3)）：
    0(根)
   / \
  1   2(根合并到0下)
     / \
    3   4

2.6 复杂度分析

操作	朴素	路径压缩	按秩合并	路径压缩+按秩合并
Find	$O(n)$	均摊 $O(\log n)$	$O(\log n)$	均摊 $O(\alpha(n))$
Union	$O(1)$	$O(1)$	$O(1)$	$O(1)$

其中 $\alpha(n)$ 是反阿克曼函数，增长极慢，实际可视为常数。

---

三、记忆与理解辅助

技巧1：并查集操作口诀

"查就找根，合就接根"

• Find：沿 parent 向上追到根
• Union：找两个根，一个挂到另一个下面

技巧2：并查集 vs 普通树的对比

对比项	并查集	普通树
关注方向	子→父（向上找根）	父→子（向下遍历）
存储方式	双亲表示法（数组存父指针）	孩子表示法/孩子兄弟法
主要操作	Find + Union	遍历 + 插入 + 删除
优化重点	降低树高（路径压缩）	—

技巧3：路径压缩的形象理解

路径压缩就像"拉平"——查找过程中把沿途所有节点都直接挂到根下面。虽然这一次查找没变快，但后续对这些节点的查找都变成了 $O(1)$。

---

四、例题与精解

例题1（基础巩固）

题目：初始有集合 {0}, {1}, {2}, {3}, {4}, {5}，依次执行以下操作，画出最终的并查集树形结构：

• Union(0, 1)
• Union(2, 3)
• Union(4, 5)
• Union(0, 3)
• Union(0, 5)

命题意图：考查并查集的合并操作和树形结构的理解。

审题分析：逐次执行合并，跟踪树形变化。

完整步骤：

Step 1：初始，6个独立集合

{0} {1} {2} {3} {4} {5}
parent: [-1, -1, -1, -1, -1, -1]

Step 2：Union(0, 1) → 1 挂到 0 下

  0       {2} {3} {4} {5}
  1
parent: [-1, 0, -1, -1, -1, -1]

Step 3：Union(2, 3) → 3 挂到 2 下

  0       2       {4} {5}
  1       3
parent: [-1, 0, -1, 2, -1, -1]

Step 4：Union(4, 5) → 5 挂到 4 下

  0       2       4
  1       3       5
parent: [-1, 0, -1, 2, -1, 4]

Step 5：Union(0, 3) → Find(0)=0, Find(3)=2 → 2 挂到 0 下

    0         4
   / \        5
  1   2
      3
parent: [-1, 0, 0, 2, -1, 4]

Step 6：Union(0, 5) → Find(0)=0, Find(5)=4 → 4 挂到 0 下

      0
    / | \
   1  2   4
      3   5
parent: [-1, 0, 0, 2, 0, 4]

答案：最终并查集为一棵以0为根的树，包含所有6个元素。

例题2（中等提升）

题目：编写带路径压缩的 Find 操作，并分析依次执行以下操作后各节点的 parent 值：

• 初始：{0}, {1}, {2}, {3}, {4}
• Union(0,1), Union(1,2), Union(2,3), Union(3,4)
• Find(4)

命题意图：考查路径压缩的具体执行过程。

审题分析：先建树，再执行 Find(4) 并观察路径压缩效果。

完整步骤：

Step 1：建立链式结构

Union(0,1): 0←1
Union(1,2): 0←1←2
Union(2,3): 0←1←2←3
Union(3,4): 0←1←2←3←4
parent: [-1, 0, 1, 2, 3]

Step 2：执行 Find(4)（路径压缩版）

// Find_Compress(S, 4)
// 第一步：找根
root = 4 → S[4]=3 → 3 → S[3]=2 → 2 → S[2]=1 → 1 → S[1]=0 → 0 → S[0]=-1
root = 0

// 第二步：路径压缩
x=4: temp=S[4]=3, S[4]=0, x=3
x=3: temp=S[3]=2, S[3]=0, x=2
x=2: temp=S[2]=1, S[2]=0, x=1
x=1: temp=S[1]=0, S[1]=0, x=0
x=0: x==root，结束

Step 3：压缩后的 parent 数组

parent: [-1, 0, 0, 0, 0]

Step 4：树形变化

压缩前：        压缩后：
  0               0
  |              /|\\\
  1            1 2 3 4
  |
  2
  |
  3
  |
  4

答案：Find(4) 后，parent = [-1, 0, 0, 0, 0]。所有节点直接指向根0。

方法反思：路径压缩的效果是"扁平化"——将链式结构变成星形结构，后续所有 Find 操作都变为 $O(1)$。

---

五、考情分析

项目	内容
考查频次	近5年约2-3次
常见题型	选择题（判断合并后的树形结构）、算法题（实现并查集操作）
分值占比	选择题2分 或 大题5-8分
命题趋势	并查集常与图论结合考查（如Kruskal算法中判断是否成环），单独出题较少但应用广泛
典型考点	①Find 和 Union 操作 ②路径压缩 ③按秩合并 ④并查集的应用（连通性判断）

---

六、易错点提醒

易错点1

• 错误表现：Union 操作时将非根节点挂到另一棵树下，而不是将根挂到根下
• 错误原因：没有先 Find 找到根
• 正确理解：Union 必须先分别找到两个元素的根，然后将一棵树的根挂到另一棵树的根下

易错点2

• 错误表现：路径压缩时只压缩了查找路径上的节点，没有将它们都挂到根下
• 错误原因：对路径压缩的理解不完整
• 正确理解：路径压缩是将查找路径上的所有节点（从 x 到根的整条路径）都直接挂到根下

易错点3

• 错误表现：混淆"按秩合并"中 S[root] 的正负含义
• 错误原因：没有理解用负数表示集合大小的设计
• 正确理解：S[root] 存储的是集合大小的相反数（负数）。比较时，S[root] 更小（绝对值更大）的集合更大，应该作为合并后的根

易错点4

• 错误表现：认为并查集的 Find 操作总是 $O(1)$
• 错误原因：高估了路径压缩的效果
• 正确理解：单次 Find 最坏 $O(n)$，但经过路径压缩后，$m$ 次操作的均摊复杂度为 $O(m\alpha(n))$

---

七、来源标注

• 依据2026考研统考408大纲
• 依据《数据结构（C语言版）》严蔚敏版
• 依据《数据结构》王道考研辅导讲义
• 并查集优化分析依据 Robert E. Tarjan 的复杂度证明