一、并查集的原理在一些应用问题中需要将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个单元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集union-findset)。比如某公司今年校招全国总共招生10人西安招4人成都招3人武汉招3人10个人来自不同的学校起先互不相识每个学生都是一个独立的小团体现给这些学生进行编号{0123456789给以下数组用来存储该小集体数组中的数字代表该小集体中具有成员的个数。毕业后学生们要去公司上班每个地方的学生自发组织成小分队一起上路于是西安学生小分队s1{0,6,7,8}成都学生小分队s2{1,4,9}武汉学生小分队s3{2,3,5}就相互认识了10个人形成了三个小团体。假设右三个群主012担任队长负责大家的出行。最后每个小队的成员就相互熟悉了,就称为朋友圈。从上图可以看出编号678同学属于0号小分队该小分队中有4人包含队长0编号为4和9的同学属于1号小分队该小分队有3人包含队长1编号为3和5的同学属于2号小分队该小分队有3个人包含队长1)。仔细观察数组中内融化可以得出以下结论数组的下标对应集合中元素的编号数组中如果为负数负号代表根数字代表该集合中元素个数数组中如果为非负数代表该元素双亲在数组中的下标在公司工作一段时间后西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起两个小圈子的学生相互介绍最后成为了一个小圈子现在0集合有7个人2集合有3个人总共两个朋友圈。通过以上例子可知并查集一般可以解决一下问题查找元素属于哪个集合沿着数组表示树形关系以上一直找到根即树中中元素为负数的位置查看两个元素是否属于同一个集合沿着数组表示的树形关系往上一直找到树的根如果根相同表明在同一个集合否则不在将两个集合归并成一个集合将两个集合中的元素合并将一个集合名称改成另一个集合的名称集合的个数遍历数组数组中元素为负数的个数即为集合的个数。二、并查集的实现HighOrderDataStruct: B树、并查集、图、LRU Cache、跳表 - Gitee.comhttps://gitee.com/Axurea/high-order-data-struct/tree/master/2026_10_09_Graph三、并查集的应用题目一LCR 116. 省份数量 - 力扣LeetCodeLCR 116. 省份数量 - 有 n 个城市其中一些彼此相连另一些没有相连。如果城市 a 与城市 b 直接相连且城市 b 与城市 c 直接相连那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected 其中 isConnected[i][j] 1 表示第 i 个城市和第 j 个城市直接相连而 isConnected[i][j] 0 表示二者不直接相连。返回矩阵中 省份 的数量。 示例 1[https://assets.leetcode.com/uploads/2020/12/24/graph1.jpg]输入isConnected [[1,1,0],[1,1,0],[0,0,1]]输出2示例 2[https://assets.leetcode.com/uploads/2020/12/24/graph2.jpg]输入isConnected [[1,0,0],[0,1,0],[0,0,1]]输出3 提示 * 1 n 200 * n isConnected.length * n isConnected[i].length * isConnected[i][j] 为 1 或 0 * isConnected[i][i] 1 * isConnected[i][j] isConnected[j][i] 注意本题与主站 547 题相同 https://leetcode.cn/problems/number-of-provinces/ [https://leetcode.cn/problems/number-of-provinces/]https://leetcode.cn/problems/bLyHh0/方法一直接使用我们写的并查集来解决这个问题class UnionFindSet { public: UnionFindSet(size_t n) :_ufs(n,-1) {} void Union(int x1,int x2) { int root1 FindRoot(x1); int root2 FindRoot(x2); // 如果本身就在一个集合就没必要合并了 if (root1 root2) return; // 让小的去做根,小的合并大的 if (root1 root2) std::swap(root1, root2); _ufs[root1] _ufs[root2]; _ufs[root2] root1; } int FindRoot(int x) { int parent x; while (_ufs[parent] 0) { parent _ufs[parent]; } return parent; } // 是不是在同一个集合 bool InSet(int x1,int x2) { return FindRoot(x1) FindRoot(x2); } // 森林里面有几棵树 size_t SetSize() { size_t size 0; for (size_t i 0; i _ufs.size(); i) if (_ufs[i] 0) size; return size; } private: std::vectorint _ufs; }; class Solution { public: int findCircleNum(vectorvectorint isConnected) { UnionFindSet ufs(isConnected.size()); for(size_t i 0;i isConnected.size();i) for(size_t j 0;j isConnected[i].size();j) if(isConnected[i][j] 1) ufs.Union(i,j); return ufs.SetSize(); } };方法二方法二如果我们遇到这种题直接写一个并查集的话会很麻烦那么我们可以使用面向过程的思想。class Solution { public: int findCircleNum(vectorvectorint isConnected) { vectorint ufs(isConnected.size(),-1); auto findRoot [ufs](int x) { while(ufs[x] 0) x ufs[x]; return x; }; for(size_t i 0;i isConnected.size();i) { for(size_t j 0;j isConnected[i].size();j) { if(isConnected[i][j] 1) { // 合并集合 int root1 findRoot(i); int root2 findRoot(j); if(root1 ! root2) { ufs[root1] ufs[root2]; ufs[root2] root1; } } } } size_t count 0; for(size_t i 0;i ufs.size();i) if(ufs[i] 0) count; return count; } };题目二990. 等式方程的可满足性 - 力扣LeetCode990. 等式方程的可满足性 - 给定一个由表示变量之间关系的字符串方程组成的数组每个字符串方程 equations[i] 的长度为 4并采用两种不同的形式之一ab 或 a!b。在这里a 和 b 是小写字母不一定不同表示单字母变量名。只有当可以将整数分配给变量名以便满足所有给定的方程时才返回 true否则返回 false。 示例 1输入[ab,b!a]输出false解释如果我们指定a 1 且 b 1那么可以满足第一个方程但无法满足第二个方程。没有办法分配变量同时满足这两个方程。示例 2输入[ba,ab]输出true解释我们可以指定 a 1 且 b 1 以满足满足这两个方程。示例 3输入[ab,bc,ac]输出true示例 4输入[ab,b!c,ca]输出false示例 5输入[cc,bd,x!z]输出true 提示 1. 1 equations.length 500 2. equations[i].length 4 3. equations[i][0] 和 equations[i][3] 是小写字母 4. equations[i][1] 要么是 要么是 ! 5. equations[i][2] 是 https://leetcode.cn/problems/satisfiability-of-equality-equations/方法一class UnionFindSet { public: UnionFindSet(size_t n) :_ufs(n, -1) ,_size(n) {} void Union(int x1,int x2) { assert(x1 0 x1 _ufs.size()); assert(x2 0 x2 _ufs.size()); int root1 FindRoot(x1); int root2 FindRoot(x2); // 如果本身就在一个集合就没必要合并了 if (root1 root2) return; // 让小的去做根,小的合并大的 if (root1 root2) std::swap(root1, root2); _ufs[root1] _ufs[root2]; _ufs[root2] root1; _size--; } int FindRoot(int x) { int parent x; while (_ufs[parent] 0) { parent _ufs[parent]; } // 压缩路径是在边找的过程中边压 // 路径压缩:将查找路径上的所有节点直接挂在根节点上 while (x ! parent) { int root _ufs[x];// 记录当前节点的父节点 _ufs[x] parent; // 让当前节点直接指向根 x root; // 继续处理原本的父节点 } return parent; } // 是不是在同一个集合 bool InSet(int x1,int x2) { return FindRoot(x1) FindRoot(x2); } // 森林里面有几棵树 size_t SetSize() { /*size_t size 0; for (size_t i 0; i _ufs.size(); i) if (_ufs[i] 0) size; return size;*/ return _size; } private: std::vectorint _ufs; size_t _size; }; class Solution { public: bool equationsPossible(vectorstring equations) { UnionFindSet _ufs(26); for(const auto e : equations) { if(e[1] ) { _ufs.Union(e[0] - a,e[3] - a); } } for(const auto e : equations) { if(e[1] !) { size_t root1 _ufs.FindRoot(e[0] - a); size_t root2 _ufs.FindRoot(e[3] - a); if(root1 root2) return false; } } return true; } };方法二class Solution { public: bool equationsPossible(vectorstring equations) { vectorint ufs(26,-1); auto findRoot [ufs](int x) { while(ufs[x] 0) x ufs[x]; return x; }; // 第一遍,先把相等的值加到一个集合中 for(const auto str : equations) { if(str[1] ) { size_t root1 findRoot(str[0] - a); size_t root2 findRoot(str[3] - a); if(root1 root2) continue; // 本身就在一个集合,就没必要再合并了 // 小的做根 // if(root1 root2) // swap(root1,root2); ufs[root1] ufs[root2]; ufs[root2] root1; } } // 第二遍,判断不相等的在不在一个集合,在就相悖,返回false for(const auto str : equations) { if(str[1] !) { size_t root1 findRoot(str[0] - a); size_t root2 findRoot(str[3] - a); if(root1 root2) return false; } } return true; } };四路径压缩在算法竞赛和工程实践中并查集Disjoint Set Union, DSU是处理不相交集合合并与查询的最强武器。而支撑其近乎 O(1)O(1) 时间复杂度的灵魂就是路径压缩与按秩合并。一、 痛点如果不做优化并查集会变成“链表”并查集的本质是一片森林每个集合是一棵树。在没有优化的情况下如果执行Union(1, 2),Union(2, 3),Union(3, 4)这棵树会退化成一条长链1 - 2 - 3 - 4。此时如果你执行Find(1)需要从 1 一路爬到 4时间复杂度退化到了 O(N)O(N)。如果数据量是 105105超时是必然的。二、 路径压缩的核心思想一句话总结在查找某个节点所在集合的根节点时顺手把查找路径上的所有节点直接挂到根节点下面。这样下一次再查找这些节点只需要一步O(1)O(1)就能找到根。图解演示假设当前树结构是1 - 2 - 3 - 44是根执行Find(1)之前执行Find(1)并经过路径压缩后路径上所有的节点都直接指向了根。三、 代码实现递归 vs 迭代路径压缩的实现有两种主流写法各有千秋。1. 递归版极简但存在爆栈风险int find(int x) { if (parent[x] x) return x; // 找到根 // 核心魔法递归回溯时把路径上的每个节点的父指针都改成根节点 return parent[x] find(parent[x]); }优点代码极短逻辑极其清晰。缺点当树深度极大时会触发系统栈溢出Stack Overflow。2. 迭代版最安全考研/工程首选之前我在手写并查集时就采用了这种迭代写法避免了爆栈问题int FindRoot(int x) { int parent x; // 1. 先一路往上找找到真正的根节点 while (_ufs[parent] 0) { parent _ufs[parent]; } // 2. 路径压缩将查找路径上的所有节点直接挂在根节点上 while (x ! parent) { int parentNode _ufs[x]; // 记录当前节点的原本父节点 _ufs[x] parent; // 让当前节点直接指向根节点 x parentNode; // 继续处理原本的父节点 } return parent; }优点无递归栈溢出风险极其安全。注意在写这段代码时变量命名要清晰比如我用parentNode而不是root避免逻辑混淆。四、 复杂度分析从 O(log⁡N)O(logN) 到 O(α(N))O(α(N))仅仅使用路径压缩查询的均摊时间复杂度是 O(log⁡N)O(logN)。如果路径压缩 按秩合并按大小合并一起使用均摊时间复杂度会降为 O(α(N))O(α(N))。α(N)α(N) 是阿克曼函数的反函数。在宇宙中所有原子数量级10801080下α(N)α(N) 都不会超过 5。因此工程上认为并查集的操作时间复杂度接近 O(1)O(1)。附录代码HighOrderDataStruct: B树、并查集、图、LRU Cache、跳表 - Gitee.comhttps://gitee.com/Axurea/high-order-data-struct/tree/master/2026_10_10_Graph笔记2026_10_09_并查集.png · Aurora/HighOrderDataStruct - Gitee.comhttps://gitee.com/Axurea/high-order-data-struct/blob/master/2026_10_09_%E5%B9%B6%E6%9F%A5%E9%9B%86.png