并查集：连通世界的高效数据结构

雪

2026-05-22 07:35:33

发布于：广东

15阅读

0回复

0点赞

—— 从原理到实战的全面解析
尊敬的各位老师、同学们：
大家好！今天，我将和大家一起深入学习一个简洁却强大、朴素却高效的数据结构 ——并查集（Union-Find Set，简称 DSU）。它被誉为 “算法界的连通神器”，以极简的代码实现、近乎常数级的时间复杂度，成为解决动态连通性问题的最优选择，广泛应用于图论、社交网络、图像处理、最小生成树等诸多领域。
在接下来的分享中，我将从起源与本质、核心操作与实现、关键优化、进阶扩展、实战应用、面试考点六个维度，由浅入深、层层递进，带大家彻底吃透并查集，让大家不仅能 “看懂原理、写出代码”，更能 “灵活运用、举一反三”。
第一部分：追本溯源 —— 并查集的诞生与本质
一、并查集的起源
并查集的理论雏形诞生于1964 年，由计算机科学家 Bernard A. Galler 和 Michael J. Fischer 首次提出，最初用于解决集合的等价类划分问题。在随后的几十年里，经过 Tarjan、姚期智等顶尖科学家的优化与论证，它逐渐成为数据结构与算法领域的经典内容，从学术研究走向工程实践，成为程序员必须掌握的基础数据结构之一。
二、什么是并查集？—— 用生活场景读懂本质
很多同学听到 “数据结构” 就觉得晦涩难懂，但并查集的核心思想，用 ** 生活中的 “帮派认亲”** 就能完美解释：
初始状态：每个人都是独立的 “小帮派”，自己就是帮派的老大（根节点）；
合并操作：两个帮派结盟，让其中一个帮派的老大归顺另一个帮派的老大，两个帮派合二为一；
查询操作：判断两个人是不是同一个帮派，只需要看他们的最终老大是不是同一个人。
从计算机科学的角度定义：并查集是一种基于森林（多棵树）实现的树形数据结构，专门用于处理不相交集合的动态合并与查询问题。
这里有两个核心关键词：
不相交集合：多个集合没有公共元素，彼此独立（比如初始时每个人的独立帮派）；
动态连通性：支持实时添加连接关系，并快速查询连通状态（比如不断结盟帮派，随时判断两人是否同属一个帮派）。
三、为什么需要并查集？—— 传统方法的痛点
为了让大家理解并查集的价值，我们先看一个经典问题：
【问题】有 n 个人，给定 m 对好友关系，每次询问两个人是否是好友（直接或间接）。
如果用传统方法解决，会面临哪些问题？
暴力枚举：每次查询遍历所有好友关系，时间复杂度 O (m)，m 很大时直接超时；
DFS/BFS：每次查询都遍历图，静态场景尚可，动态添加关系时效率极低；
数组标记：用数组记录集合编号，合并时需要遍历整个数组修改编号，时间复杂度 O (n)。
而并查集，通过树形结构 + 优化技巧，能让合并、查询操作的均摊时间复杂度接近 O (1)，完美解决动态连通性问题。这就是并查集存在的意义 ——用最简单的方式，解决最棘手的连通问题。
第二部分：核心筑基 —— 并查集的基本操作与实现
并查集的核心只有三个基本操作：初始化、查找、合并。所有复杂的应用，都是这三个操作的延伸。我们以数组实现为例（最常用、最简洁），一步步拆解。
一、核心数据结构
并查集的实现仅需一个一维数组，我们称之为父节点数组 parent []：
parent [i]：表示元素 i 的父节点；
规则：如果 parent [i] = i，说明 i 是当前集合的根节点（帮派老大）。
二、三大基本操作

初始化（Init）
初始时，每个元素都是独立的集合，自己的父节点就是自己。
代码实现（C++）：

const int MAXN = 10005;
int parent[MAXN]; // 父节点数组
// 初始化n个元素
void init(int n) {
    for (int i = 1; i ++) {
        parent[i] = i; // 每个元素的父节点是自己
    }
}

逻辑：1~n 每个元素自成一派，根节点都是自身。
2. 查找（Find）—— 找根节点
查找操作的核心：找到一个元素所在集合的根节点（判断帮派老大）。
基本逻辑：如果当前元素不是根节点，就递归 / 迭代向上找父节点，直到找到根节点。
未优化代码（递归实现）：

// 查找元素x的根节点
int find(int x) {
    // 递归终止：找到根节点
    if (parent[x] == x) return x;
    // 否则继续找父节点的根节点
    return find(parent[x]);
}

未优化代码（迭代实现）：

int find(int x) {
    while (parent[x] != x) {
        x = parent[x]; // 向上遍历父节点
    }
    return x;
}

关键：查找是并查集的核心操作，后续的优化都围绕查找展开。
3. 合并（Union）—— 合并两个集合
合并操作的核心：将两个不相交的集合合并为一个集合。
基本逻辑：
分别找到两个元素的根节点；
如果根节点不同，让一个根节点的父节点指向另一个根节点（一个帮派老大归顺另一个）。
未优化代码：

// 合并x和y所在的集合
void unite(int x, int y) {
    int rootX = find(x); // 找x的根
    int rootY = find(y); // 找y的根
    // 根不同，合并两个集合
    if (rootX != rootY) {
        parent[rootX] = rootY; // rootX的父节点变为rootY
    }
}

补充：判断两个元素是否连通，只需判断find(x) == find(y)即可。
三、基本实现的缺陷
看似完美的基本实现，却存在致命问题：树的高度会不断增加，甚至退化成链表。
比如依次合并 1-2、2-3、3-4…… 最终树会变成一条链：1←2←3←4←……←n。
此时查找操作的时间复杂度会退化为O(n)，完全失去并查集的效率优势。
这就引出了并查集的两大核心优化：路径压缩和按秩合并。这两个优化，是并查集实现 “近乎 O (1)” 效率的关键。
第三部分：效率飞跃 —— 并查集的两大核心优化
并查集的优化，本质是让树尽可能 “扁平”，减少查找时的遍历层数。两大优化可以单独使用，也可以组合使用（组合后效率最优）。
一、优化一：路径压缩（Path Compression）——“一步到位找老大”

优化思想
在查找根节点的过程中，顺手将路径上的所有节点直接指向根节点，让树的高度直接变为 2 层（根节点 + 子节点）。
比如查找 3 的根节点：3→2→1（根），路径压缩后，3 和 2 的父节点直接变为 1，下次查找直接一步到位。
两种实现方式
（1）完全路径压缩（最常用，递归）
查找时，将路径上所有节点直接指向根节点，压缩最彻底。

int find(int x) {
    if (parent[x] != x) {
        // 递归找根，同时将当前节点的父节点直接设为根节点（路径压缩）
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

（2）隔代路径压缩（迭代）
查找时，将当前节点指向祖父节点，两步一压缩，实现简单。

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]]; // 隔代压缩：指向祖父节点
        x = parent[x];
    }
    return x;
}

优化效果
路径压缩后，树的高度大幅降低，单次查找时间复杂度接近 O (1)，彻底解决链表退化问题。
二、优化二：按秩合并（Union by Rank）——“小树贴大树”
优化思想
合并两个集合时，不随意合并，而是将 **“秩” 较小的树合并到 “秩” 较大的树上 **，避免树的高度过快增长。
这里的 “秩” 有两种定义：
按深度合并：秩 = 树的高度；
按大小合并：秩 = 集合的节点个数（更常用，效果一致）。
实现步骤
新增一个数组：
rank []：记录每个根节点对应树的高度（按深度合并）；
size []：记录每个根节点对应集合的节点数（按大小合并）；
初始化：rank [i] = 1，size [i] = 1（每个树初始高度 / 大小为 1）；
合并时：比较两个根节点的秩，将小秩树的根指向大秩树的根。
代码实现（按大小合并，最常用）

int parent[MAXN];
int size_[MAXN]; // 记录每个集合的节点数，避免与关键字size冲突

// 初始化
void init(int n) {
    for (int i = 1; i ; i++) {
        parent[i] = i;
        size_[i] = 1; // 初始每个集合只有1个节点
    }
}

// 查找（带路径压缩）
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// 合并（按大小合并）
void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return; // 已在同一集合，无需合并
    
    // 小树合并到大树上：保证树的高度不增加
    if (size_[rootX] < size_[rootY]) {
        swap(rootX, rootY); // 确保rootX是大树
    }
    parent[rootY] = rootX; // 小树的根指向大树的根
    size_[rootX] += size_[rootY]; // 更新大树的节点数
}

优化效果
按秩合并从合并环节控制树的高度，即使不做路径压缩，单次操作时间复杂度也能达到O(logn)。
三、双优化组合 —— 终极高效并查集
路径压缩 + 按秩合并，是并查集的终极形态。
经过数学证明，这种组合下，并查集的单次操作时间复杂度为 O (α(n))，其中 α(n) 是反阿克曼函数—— 这个函数增长极其缓慢，对于宇宙中所有原子数量级的 n，α(n) 都不超过 5。
也就是说：在实际应用中，优化后的并查集，合并、查询操作都是常数级时间！
四、完整模板代码（C++）
这是算法竞赛、工程开发中最常用的并查集模板，直接背诵即可：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
int parent[MAXN];
int size_[MAXN];

// 初始化
void init(int n) {
    for (int i = 1; i ++) {
        parent[i] = i;
        size_[i] = 1;
    }
}

// 查找（路径压缩）
int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

// 合并（按大小合并）
bool unite(int x, int y) {
    int rx = find(x);
    int ry = find(y);
    if (rx == ry) return false; // 合并失败，已连通
    // 小树贴大树
    if (size_[rx] < size_[ry]) swap(rx, ry);
    parent[ry] = rx;
    size_[rx] += size_[ry];
    return true; // 合并成功
}

// 判断是否连通
bool isConnected(int x, int y) {
    return find(x) == find(y);
}

int main() {
    int n, m;
    cin >> n >> m;
    init(n);
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) unite(x, y); // 合并
        else cout <Connected(x, y) ? "YES" : "NO") <
    }
    return 0;
}

第四部分：进阶突破 —— 带权并查集与扩展域并查集
基础并查集只能处理 **“是否连通”的二元关系，但实际问题中，往往存在带权值、多类型的关系。这时就需要进阶并查集 **：带权并查集和扩展域并查集。
一、带权并查集（Weighted DSU）—— 维护节点间的权值关系

适用场景
处理节点间存在数值关系的问题，比如：
A 和 B 的距离是多少；
A 比 B 大多少；
食物链中的 “吃与被吃” 关系。
核心思想
在基础并查集上，新增一个权值数组 weight []：
weight [x]：表示节点 x 到其父节点的权值；
查找 / 合并时，同步更新权值，维护节点到根节点的权值关系。
经典案例：食物链（NOI2001）
问题：有三类动物 A、B、C，A 吃 B，B 吃 C，C 吃 A。给定 n 个动物，m 句话，判断假话数量。
思路：用带权并查集维护动物间的关系，weight [x]%3=0 表示与根同类，=1 表示吃根，=2 表示被根吃。
核心：查找时更新权值，合并时根据关系列方程计算权值。
关键代码（带权查找）

int find(int x) {
    if (parent[x] != x) {
        int orig_parent = parent[x]; // 记录原父节点
        parent[x] = find(parent[x]); // 路径压缩
        weight[x] += weight[orig_parent]; // 更新x到根的权值
    }
    return parent[x];
}

二、扩展域并查集（Extended DSU）—— 一人多域，处理多关系

适用场景
处理 “不能同组、必须不同组” 的多关系问题，比如：
关押罪犯：两个罪犯不能关在同一个监狱；
二分图判定：节点分为两组，相邻节点不同组。
核心思想
给每个元素拆分多个 “分身”（扩展域），每个分身代表一种状态，通过合并分身表示关系。
比如：关押罪犯问题，给每个罪犯 x 拆分为：
x：表示 x 在监狱 A；
x+n：表示 x 在监狱 B。
若 x 和 y 不能同监狱，则合并 x 与 y+n，x+n 与 y。
经典案例：关押罪犯（NOIP2010）
问题：n 个罪犯，m 对仇恨关系，仇恨值越大越不能关一起，求最小的最大仇恨值。
思路：按仇恨值从大到小排序，用扩展域并查集判断两人是否已被分配到同一监狱，若矛盾则输出当前仇恨值。
三、进阶并查集总结
带权并查集：解决带权值、有数值关系的问题，核心是维护 weight []；
扩展域并查集：解决多类型、互斥关系的问题，核心是拆分元素域；
本质：都是基础并查集的扩展，核心操作依然是查找与合并。
第五部分：实战落地 —— 并查集的经典应用场景
并查集的应用无处不在，只要涉及动态连通、集合划分、连通块统计，都能看到它的身影。下面我们梳理六大经典应用，结合案例讲解。
一、应用一：社交网络关系分析（最经典场景）
场景：微信 / QQ 好友关系，判断两人是否是 “间接好友”，统计朋友圈数量。
抽象：用户 = 节点，好友关系 = 边，朋友圈 = 连通分量。
实现：
初始化并查集，每个用户为独立节点；
每添加一对好友，执行合并操作；
查询两人是否好友：判断根节点是否相同；
统计朋友圈数量：遍历所有节点，统计根节点的个数。
二、应用二：图论 —— 无向图判环与连通块统计
无向图判环（冗余连接）
问题：给定无向图，判断是否存在环，找到冗余边。
思路：遍历每条边，若边的两个端点已连通，说明加入该边会形成环；否则合并两个端点。
例题：LeetCode 684. 冗余连接。
连通块统计
问题：统计无向图中连通分量的个数。
思路：初始化连通块数为 n，每成功合并一次，连通块数减 1，最终结果即为答案。
三、应用三：最小生成树 ——Kruskal 算法核心
最小生成树（MST）：带权无向图中，总权值最小、无环、连通所有节点的树。
Kruskal 算法是求 MST 的经典算法，核心依赖并查集：
将所有边按权值从小到大排序；
遍历每条边，用并查集判断两个端点是否连通；
若不连通，保留该边，合并两个端点；
直到选中 n-1 条边，得到最小生成树。
优势：Kruskal 算法时间复杂度为 O (mlogm)（排序为主），并查集让判环操作近乎 O (1)，效率极高。
四、应用四：图像处理 —— 连通区域标记
场景：黑白图像中，标记相邻的白色像素块（连通区域）。
抽象：像素 = 节点，相邻（上下左右）= 边，连通像素块 = 连通分量。
实现：遍历所有像素，将相邻白色像素合并，最终统计连通块数量，完成标记。
五、应用五：网格问题 —— 岛屿数量统计
问题：二维网格中，1 表示陆地，0 表示水，统计岛屿数量（上下左右相邻陆地为一个岛屿）。
思路：将二维坐标映射为一维编号（i*m + j），用并查集合并相邻陆地，最终统计连通块数。
例题：LeetCode 200. 岛屿数量。
六、应用六：工程领域 —— 网络连通性检测
场景：计算机网络中，检测两台设备是否连通；分布式系统中，节点集群的动态划分。
实现：设备 = 节点，网络连接 = 边，用并查集动态维护连通状态，快速查询连通性。
七、应用总结
并查集的核心价值：用极简代码，高效解决动态连通性问题。
它不依赖复杂的数据结构，不涉及高深算法思想，却能在算法竞赛、工程开发、学术研究中大放异彩，这就是 “简单即强大” 的最好诠释。
第六部分：面试考点 —— 并查集高频问题解析
并查集是程序员面试、算法笔试的高频考点，下面梳理五大核心面试题，帮大家轻松应对。
一、基础面试题
并查集的核心操作是什么？
答：初始化、查找（找根）、合并（集合合并），核心是动态维护连通性。
并查集的两大优化是什么？原理分别是什么？
答：路径压缩（查找时让节点直接指向根，扁平化树）；按秩合并（合并时小树贴大树，控制树高）。
并查集的时间复杂度是多少？α(n) 是什么？
答：双优化后单次操作 O (α(n))，α(n) 是反阿克曼函数，增长极慢，实际视为 O (1)。
二、代码面试题
手写优化后的并查集模板
答：直接写第三部分的完整模板代码，重点体现路径压缩和按大小合并。
用并查集解决 “岛屿数量” 问题
答：二维转一维，合并相邻陆地，统计连通块数。
三、进阶面试题
带权并查集和扩展域并查集的区别？
答：带权并查集维护数值权值关系，扩展域并查集维护多类型互斥关系。
并查集能处理动态删除边吗？为什么？
答：不能。并查集是 “单向合并” 结构，合并后无法高效拆分，删除边需要更复杂的数据结构（如 Link-Cut Tree）。
第七部分：总结升华 —— 并查集的思想与价值
一、并查集的核心思想
树形抽象：用森林表示不相交集合，根节点作为集合代表；
扁平化优化：通过路径压缩、按秩合并，让结构尽可能简单；
动态高效：以最小的代价，解决动态连通性问题。
二、并查集的学习启示
并查集告诉我们：优秀的算法，从来不是复杂的堆砌，而是简洁的极致。
它没有华丽的语法，没有复杂的逻辑，却用最朴素的数组、最简洁的循环递归，解决了最棘手的问题。这正是计算机科学的魅力 ——化繁为简，直击本质。
三、学习建议
先记模板：背诵双优化并查集代码，做到 “闭眼写”；
再练基础：刷模板题（洛谷 P3367）、好友关系、判环问题；
后攻进阶：学习带权并查集、扩展域并查集，攻克食物链、关押罪犯等难题；
结合应用：理解 Kruskal 算法、社交网络等场景，做到学以致用。
第八部分：结尾致谢
各位老师、同学们，今天我们从并查集的起源、本质、基本操作、核心优化、进阶扩展、实战应用、面试考点，全方位学习了这个经典的数据结构。
并查集虽小，却蕴含着数据结构的核心智慧；代码虽简，却能解决万千连通难题。希望大家通过今天的分享，不仅掌握并查集的知识，更能体会到简洁、高效、实用的算法精神。
最后，感谢大家的认真聆听！如果大家有任何问题，欢迎随时交流探讨。谢谢大家！
求关注
~~@椰丝CO(关注我的都是我跌)~~
~~帮这位也求一个~~
美味的知识