你有没有想过，怎么用一个数据结构，把"一堆人里，谁和谁是一个圈子"这件事管好？比如公司校招招了 10 个毕业生，分别来自五个地方，刚到岗谁都不认识谁，那这时候每一个人都是独立的"小团体"。后来西安的四个人混熟了、结伴出行，成都的、武汉的也各自抱团，于是人群被划分成了几个"朋友圈"。再后来跨城市的人又走动起来，不同的圈子合并成一个。你需要在任何时候都能快速回答两件事：某个同学属于哪个圈子、两个同学是不是同一个圈子。这就是并查集要干的事。
并查集英文叫 union-find set，中文直译就是"合并 + 查找"，这个名字把它的全部能力都写在脸上了。它是一个非常"朴素"却极其能打的数据结构——不靠复杂的指针、不靠旋转、连树的高度都不是精确维护的，却能在各种比赛和算法题里被用到几乎"无招胜有招"。这一篇，我们把它彻底讲透。
先铺垫：集合、不相交集合和"根"
正式写代码之前，先把几个词定义清楚，因为你后面会反复撞见它们，撞见一次就要懂一次。
集合（set），就是一堆互不相同元素的"抱团"。在并查集的语境里，我们说的集合是更具体的一种：不相交集合（disjoint set）。什么叫不相交？就是任意两个集合之间没有任何共同的元素——元素 x 要么属于集合 A，要么属于集合 B，绝不脚踏两只船。把 10 个学生划分成西安、成都、武汉三个小分队，这三队之间两两没有重叠，它们就是一组不相交集合。
在这种划分下，每个元素都属于恰好一个集合。那么"查询某个元素属于哪个集合"这件事就有了一个非常优雅的等价说法：给每个集合指定一个"队长"（代表元，英文 representative），查询归属就变成"找队长"。谁是一个集合的队长？在并查集里，我们让每个集合里某个特殊的元素来当"根"（root）。于是并查集的所有操作，最后都收敛到一句话上：
找到这个元素所在那棵树的"根"。
你可能会疑惑：怎么又是一个树？分组不是线性的吗？别急，我马上给你看，并查集是怎么用一个一维数组，在背后偷偷搭起一棵（可能很丑的）树来的——而树，正是"找到根"这个动作能高效的物理基础。
用数组搭树：负号是根，正数是父亲
并查集的经典实现，只用一个一维数组就够了。我们还是拿校招 10 个学生来讲，给他们编号 0, 1, 2, 3, ..., 9，用这个编号当数组的下标。数组里每个格子存一个 int，它的含义分两种：
- 如果
_ufs[i]是负数，说明下标i这个位置是一个根（队长），而这个负数的绝对值就是它这一队有多少人。 - 如果
_ufs[i]是非负数，说明下标i这个元素不是根，它存的数字是它"父亲"在数组里的下标。
关键就在"父亲"这两个字上。你顺着一个人，去看它存的下标，跳到父亲的位置，再看那个位置的数字，再跳……一路往上"爬"，只要爬到的位置存的是负数，那就是爬到根了。这就是一棵"从儿子指向父亲"的树——和我们平常写的"根指向儿子"的树方向正好相反，但本质一样，只是我们把指针"倒过来"用而已。把树的父子关系编码进一个 int 数组，这就是并查集空间上极省的秘密：O(n) 个 int 就管起了一整片森林。
初始时每个人都自成一队、自己就是自己的队长，所以把数组每一项都设成 -1（自己是根，队伍里就自己 1 个人）：
下标: 0 1 2 3 4 5 6 7 8 9
值: -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
假设后来 {0,6,7,8} 成了一个小队（队长 0），{1,4,9} 成了小队（队长 1），{2,3,5} 成了小队（队长 2）。那么数组会变成：
下标: 0 1 2 3 4 5 6 7 8 9
值: -4 -3 -3 2 1 2 0 0 0 1
我来陪你读一遍：_ufs[0] = -4，说明 0 是根，这一队有 4 人；_ufs[6] = 0 是正数，说明 6 的父亲是 0；_ufs[7] = 0、_ufs[8] = 0 同理，它们都挂在 0 下面。所以 {0,6,7,8} 里只有 0 是根，其余的都指向 0。再看 3、5 指向 2，而 2 存的是 -3——2 是根、三人一队。这样一根一根数下来，负数的个数就是有几个团队，这个结论我们待会还会用到。
这套"负号是根、正数是父亲"的编码，是整个并查集的根基，请你把它死死记住。接下来的所有实现，都只是围绕这根柱子转。
支持的操作：查找、判断、合并、计数
先把并查集这个抽象数据类型到底"卖什么服务"列清楚，再看代码，你就知道每段代码是干谁的活。一共四件事：
- 查归属：给定一个元素编号，找到它所在集合的"根"。方法是顺着一路找父亲，直到负数。
- 判同类：判断两个元素是否在同一集合。做法是分别找两个根，根相同就在一起。
- 合并：把两个集合并成一个。先找两个根，若不同，就把一个根的军队并到另一个的旗号下。
- 计数：现在一共有几个集合。数一数数组里有几个负数即可。
你发现没有，前两个操作本质是同一件事（都是 FindRoot），合并和判断也共享"找根"这个基础动作。所以整棵并查集的代码，核心其实就一个函数——FindRoot（找根）。把根找到了，其余全是顺水推舟。
下面我们先写一个最"朴素"、没有任何优化的版本，把逻辑走通，然后再一步步给它装上两件神装：路径压缩和按秩合并。
朴素实现：Find 与 Union
先看最直白的找根。前面约定过：_ufs[index] >= 0 就说明 index 不是根，它存的是父亲的编号，所以要么继续往上跳，直到遇到一个负数单元格。
// 朴素版《找根》：顺着父亲指针一路爬到顶，返回根的编号
int FindRoot(int index)
{
while (_ufs[index] >= 0) // 当前格不是根（存的非负 = 父亲下标）
{
index = _ufs[index]; // 爬到父亲的位置，继续判断
}
return index; // 此刻 _ufs[index] < 0，它就是根
}看懂这段，你已经在写并查集了。它背后就是那棵树里"从儿子一路爬到根"的路径。
再写合并。合并的思路很直白：找出两个人的根，只要不是同一个根，就说明他们分属两个圈子，那就把两个圈子的军队并到一起。**谁来当新队长？**朴素版本里我们为了简单，就先让 root1 当新根：把 root1 那队的人数（负数）加上 root2 那队的人数，然后把 root2 的位置改成指向 root1。这样 root1 成了新队长，队伍人数也更新对了。
// 朴素版《合并》：把 x1 和 x2 所在的两个集合并成一个，返回是否真的发生了合并
bool Union(int x1, int x2)
{
int root1 = FindRoot(x1); // 找 x1 的队长
int root2 = FindRoot(x2); // 找 x2 的队长
if (root1 == root2) // 队长是同一个人：本来就在一个圈子
return false; // 无事可做，返回 false 表示"没合并成"
_ufs[root1] += _ufs[root2]; // root1 队的人数累加 root2 队的人数（注意都是负数）
_ufs[root2] = root1; // 让 root2 认 root1 当父亲，两个圈并成一个
return true; // 合并成功
}数集合个数的 Count 也一并给你，它就是遍历数组数负数，一行心法：
// 统计一共有几个集合：数数组中负数的个数
size_t Count() const
{
size_t count = 0; // 计数器归零
for (auto e : _ufs) // 遍历整个数组
{
if (e < 0) // 是负数就是根，也就是一个集合的队长
++count;
}
return count; // 负数的数量即集合的数量
}到这里，一套能用的并查集已经齐了。但它有个隐患——如果合并的顺序很倒霉，树会退化成一条长长的链。比如不断地把"新集合"往老根上挂，每个元素都连成一串，那么 FindRoot 最坏要一路走到底，退化成 O(n)。这就有点浪费了。别急，接下来两件神装专门收拾这个问题。
神装一：路径压缩，把树拍扁
先想清楚一个"套路化"的问题：FindRoot 的返回值只有根一个，而这里面最耗时的，恰恰是从某个元素一路爬到根所走过的那条路。如果这条路上有 1000 个点，每次查一次走 1000 步，那合并一多就惨了。
路径压缩（path compression）的思路非常朴素，却聪明到骨子里：既然每次 FindRoot 都要从某个结点一路爬到根，那我爬完之后，随手把这路上的每一个结点，都直接改成"父亲就是根"不就行了？ 这样以后再查这棵树里的任何一个结点，一跳就到根，O(1)。
用代码实现按"递归 + 回溯过程中改父亲"最优雅：
// 递归版《带路径压缩的找根》：找到根后，沿途所有结点直接挂到根下
int FindRoot(int index)
{
if (_ufs[index] < 0) // 负值即根
return index; // 根就是它自己
int root = FindRoot(_ufs[index]); // 先递归找根的根
_ufs[index] = root; // 回溯：把当前结点父亲直接改成根（压缩）
return root; // 返回根编号
}这段代码我逐行给你念：if (_ufs[index] < 0) return index 是递归出口，遇到根就回；否则先递归找 _ufs[index]（父亲）的根，等递归回来，_ufs[index] 已经被赋成了根——注意，回溯是自下而上的，最深处的子结点先把父亲改成根，一层层弹回来，这中间每个结点都顺带把自己也改成了根。所以你调用一次 FindRoot，整条祖先链上所有结点的父亲都被改写成了根。这就是"压缩"两个字的含义——把原来又高又瘦的一条链，压成了一片"贴地"的放射状结构。
不过递归在极端长链上可能撑爆系统栈，很多工程实现更喜欢非递归版本的两趟法：第一趟顺着爬、把沿途经过的结点都记下来；第二趟再把它们逐个改指向根。这里给你一个不额外开数组、只用一个临时变量的简洁写法：
// 非递归版《带路径压缩的找根》：先找根记住根，再沿原路把所有结点挂到根下
int FindRoot(int index)
{
int child = index; // 暂存原始起点，压缩时要沿这条路回改
while (_ufs[index] >= 0) // 第一趟：先爬到根
index = _ufs[index];
// 到此 index 就是根
int root = index;
// 第二趟：沿着原始路径从起点一路改到根，把沿途父亲的父亲……都改成根
while (_ufs[child] >= 0) // 还没爬到根，就继续改
{
int parent = _ufs[child]; // 记下 child 的原父亲
_ufs[child] = root; // 把 child 直接挂到根下（压缩）
child = parent; // 继续处理原父亲
}
return root; // 返回根
}注意第一个 while 之后 index 已经是根了，而 child 还停留在最开始的起点。第二个 while 从 child 出发，一步一步把这条路上的每个结点都改成指向 root，同时用 parent 保存它原来的父亲以便继续往上，直到爬到根为止。两趟走完，这条路被彻底拍扁。
有了路径压缩，树的"高度"在实践中会非常非常低。但请注意，路径压缩只在 FindRoot 被调用时才触发——如果你一直只 Union 不 Find，丑树还是会越挂越高。这就引出第二件神装，从源头就把树尽量长"矮"。
神装二：按秩合并，让树矮下去
按秩合并（union by rank）想解决的是另一个方向的问题：合并时到底让谁当新根，才不容易把树挂成又高又瘦的单链？
直观答案很朴素：让"矮"的树挂到"高"的树下面。因为树高决定了 FindRoot 一步需要爬多高。如果把高树挂到矮树下面，高树整体又高了一层，更糟；反过来把矮树挂到高树下面，高度增加得少，甚至不增加。这是我们从小就懂的道理：个子高的当队长，个子矮的当队员，队伍整体才不至于被越垫越高。
那么"秩（rank）"是什么？你可以把它理解成"这棵树大概有多高"的一个评价值。有两套常见的口径：
- 以集合大小（size）为秩：队伍里有多少人，人多就是"胖"。
- 以树的近似高度为秩：树有几层，层深就是"高"。
两套都管用，工程上以大小为秩往往更省心，因为高度随着路径压缩会飘忽不定，而大小是稳定的（合并后直接相加）。这里我按老师课件那套"数组中存负集合大小"的约定来，负数的绝对值即是秩——合并时，谁人少谁就投靠人多的。
按大小合并的 Union 是这样的——注意我们对负号系统的巧妙复用：
// 按大小(负重)合并：人少的集合挂到人多的集合下面，让树不容易长高
bool Union(int x1, int x2)
{
int root1 = FindRoot(x1); // 找 x1 的根（顺带做了一次路径压缩）
int root2 = FindRoot(x2); // 找 x2 的根
if (root1 == root2) // 已经在一个集合
return false;
// _ufs[root] 是负的，互为相反数比较大小。这里让 root1 指向"人更多"的根
if (_ufs[root1] > _ufs[root2]) // root1 的人数(绝对值)更少
std::swap(root1, root2); // 交换：保证 root1 是人数更多(更"胖")的那个根
_ufs[root1] += _ufs[root2]; // 把 root2 那队人数并入 root1（负数相加）
_ufs[root2] = root1; // 人数少的 root2 挂到人数多的 root1 下
return true;
}请仔细品一下 if (_ufs[root1] > _ufs[root2]) std::swap(root1, root2); 这一句。因为 _ufs[root] 存的是负数，所以"人更多"反而对应"值更小"（例如 -5 比 -3 更小）。我们要让小树挂大树，也就是让人数多的当新根。_ufs[root1] > _ufs[root2] 意味着 _ufs[root1] 更大、绝对值更小、人更少，于是交换，让 root1 变成人多的那个。交换之后，下面两行才"放心"地把 root2 军队并入 root1。逻辑里全是负号的坑，我建议你拿纸笔用两个具体数（比如 root1 队 3 人、root2 队 5 人）推一遍：初始 _ufs[root1]=-3, _ufs[root2]=-5，-3 > -5 成立，交换后 root1 变成原来人多的那个，于是 root2（3 人）挂到 root1（5 人）下面，正确。
按秩合并 + 路径压缩，这两件神装一合体，并查集体型就被死死压住了。它的实际复杂度有多恐怖？下一节见分晓。
复杂度：为什么是近似的 O(α(n))
说到复杂度，很多教程直接甩给你一句"近似 O(1)"或"O(α(n))"，然后就没了。这里我们把话说明白，让你不仅会背，还知道 α 从哪来。
先感受一个事实：没有合并、只有压缩的时候，单次 FindRoot 最坏是 O(log n)（树是二叉树时），甚至可以证明更紧。而有了按秩合并，即使不做压缩，任意一棵树的高度也被限制在 O(log n) 之内（因为一个集合的树高只在"合并两棵等高的树"时才会加 1，而这种情况每发生一次，集合大小就至少翻一倍，所以高度增长是极慢的对数级）。然后再加上路径压缩，两者叠加，就产生了一个极其离谱的摊还结论——
做 m 个"Find + Union"操作（其中最多 n-1 次 Union），总时间复杂度是 O(m · α(n))，其中 α(n) 是反阿克曼函数（inverse Ackermann function）。
反阿克曼函数这个名字听起来很吓人，但它的数值小到你无法想象。阿克曼函数本身是一个增长快得离谱到"反人类"的函数——它即使只用很小的下标（连 A(4,4) 都已经是一个天文数字级别的巨大数），产生的数值也大到用常规符号都写不下；而反阿克曼函数就是它"逆"过来，因此增长慢得几乎等于不动。给你一组直观数字：α 在 n 等于整个可见宇宙原子数数量级时，也不会超过 4 或 5。也就是说，在实际应用里你可以把单次操作的时间当成"常量"，这就是为什么很多老手会直接跟你说并查集"几乎是 O(1)"。
严格证明这个上界需要用到相当深的势能分析，超出了本文（以及绝大多数应用场景）的射程，你只要抓牢两个结论即可：一是记住复杂度上界是 O(m·α(n))；二是理解实际运行中肉眼观感就是常数时间。
还要补充一个容易记错的点：如果你只做按秩合并、不做路径压缩，复杂度是 O(m log n)；如果你只做路径压缩、不做按秩合并，最坏情况（数据故意针对你）会退化。两个都用才是最优，缺一不可，这是考场和面试里常见的追问。
完整可编译的 union_find 类
下面给你一个训练完整、每行都有注释、可以直接复制进编译器运行的 union_find 类。它把你上面学的所有东西——父子数组、秩（负集合大小）、递归与非递归两种带路径压缩的找根、按秩合并、计数，以及若干应用演示——一次性整合在一起。
#include <iostream>
#include <vector>
#include <string>
#include <utility> // std::swap
class UnionFind
{
public:
// 构造：n 个元素，初始每个都自成一队（自己是根，队里就自己）
// _ufs[i] < 0 表示 i 是根，绝对值是集合大小；>= 0 表示父亲下标
explicit UnionFind(size_t n)
: _ufs(n, -1)
{}
// 递归版《带路径压缩的找根》：回溯时把沿途结点全部直挂到根下
int FindRootRecursive(int index)
{
if (_ufs[index] < 0) // 负值即根
return index; // 根就是自己
int root = FindRootRecursive(_ufs[index]); // 先递归找根的根
_ufs[index] = root; // 回溯：直接把父亲改成根（压缩）
return root; // 向上层返回根
}
// 非递归版《带路径压缩的找根》：两趟法，先把路径记下再沿途挂到根
int FindRoot(int index)
{
int child = index; // 暂存起点，压缩时要沿原路回改
while (_ufs[index] >= 0) // 第一趟：爬到根
index = _ufs[index];
int root = index; // 此刻 index 即根，记下来
while (_ufs[child] >= 0) // 第二趟：从起点沿路把所有结点挂到根
{
int parent = _ufs[child]; // 记下 child 的原父亲
_ufs[child] = root; // child 直接挂到根下（压缩）
child = parent; // 继续处理原父亲
}
return root; // 返回根
}
// 按大小合并（负集合大小为秩）：人少的挂到人多的之下，防止树长高
bool Union(int x1, int x2)
{
int root1 = FindRoot(x1); // 找 x1 的根并压缩
int root2 = FindRoot(x2); // 找 x2 的根并压缩
if (root1 == root2) // 本就是同一集合
return false; // 无需合并
if (_ufs[root1] > _ufs[root2]) // root1 人数(绝对值)更少就交换
std::swap(root1, root2); // 保证 root1 是人数多的根
_ufs[root1] += _ufs[root2]; // root2 队人数并入 root1（负数相加）
_ufs[root2] = root1; // root2 挂到 root1 之下
return true; // 真的发生了合并
}
// 两个元素是否在同一个集合
bool IsConnected(int x1, int x2)
{
return FindRoot(x1) == FindRoot(x2); // 根相同即同一集合
}
// 当前一共有几个集合：数负数即可
size_t Count() const
{
size_t cnt = 0; // 计数器
for (auto e : _ufs) // 遍历数组
if (e < 0) // 负值 = 根的标志
++cnt; // 每发现一个根就是一个集合
return cnt;
}
// 打印当前数组内部形态，方便观察/调试（打印的是数组值不是集合）
void DebugPrint() const
{
for (size_t i = 0; i < _ufs.size(); ++i)
std::cout << i << ":" << _ufs[i] << " "; // 输出每个格子的值
std::cout << std::endl;
}
private:
std::vector<int> _ufs; // 核心一维数组：负数为根，非负数为父亲下标
};FindRoot 与 FindRootRecursive 我会两个都保留，正是为了让你对比：递归版更短更优雅，但深度很深的链有栈溢出风险；非递归版稍长，却结构稳健、不怕长链，工程上我更推荐它。你二选一即可，效果完全相同。
配套一个验证用的小 main，跑一圈你就能亲眼看到合并、计数、判同类的每一步：
int main()
{
UnionFind uf(10); // 10 个学生，初始互相都不认识
uf.Union(0, 1); // 0 和 1 认识，合并
uf.Union(1, 2); // 1 和 2 认识，合并（间接 0,1,2 一团）
uf.Union(3, 9); // 3 和 9 认识，合并
std::cout << "当前集合数: " << uf.Count() << std::endl; // 应输出 7
std::cout << "0 与 2 是否同集合: "
<< (uf.IsConnected(0, 2) ? "是" : "否") << std::endl; // 是
std::cout << "0 与 3 是否同集合: "
<< (uf.IsConnected(0, 3) ? "是" : "否") << std::endl; // 否
uf.Union(2, 3); // 再把两个大团合并
std::cout << "合并后集合数: " << uf.Count() << std::endl; // 应输出 6
std::cout << "0 与 9 是否同集合: "
<< (uf.IsConnected(0, 9) ? "是" : "否") << std::endl; // 是
// 演示 Union 在已同集合时返回 false
std::cout << "重复合并返回值: "
<< (uf.Union(0, 9) ? "true" : "false") << std::endl; // false
return 0;
}把类定义和这个 main 合到一起，一次编译、直接跑通。看到输出分别是 7 / 是 / 否 / 6 / 是 / false，就说明这套并查集工作正常。简单核对这个数字：10 个元素，前 3 次合并成功各吃掉一个集合（10→9→8→7），第 4 次 Union 又把两个已有的集合并成了一个，所以集合数从 7 再减 1 到 6。
应用一：省份数量（朋友圈）
现在登场的是最经典的一道并查集应用题，它的小名叫"朋友圈"：给你一个 n × n 的 isConnected 矩阵，isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连。问一共能划分成多少个"省份"（连通集合）？
思路一句话：遍历矩阵右上三角，凡是有边相连且尚不在同一集合的两个城市就 Union，最后数集合个数即可。 为什么只看右上三角？因为矩阵是对称的，isConnected[i][j] == isConnected[j][i]，i 与 j 相连的信息在第 i 行出现过、第 j 行又出现一遍，我们只需要处理一边，避免重复合并；当然对角线恒为 1，自己和自己不必合并。
#include <iostream>
#include <vector>
// 省份数量：isConnected[i][j]==1 表示 i、j 连通，求连通集合个数
int findCircleNum(std::vector<std::vector<int>>& isConnected)
{
int n = static_cast<int>(isConnected.size()); // 城市数量
// 手动并查集：初始每个城市自成一省
std::vector<int> ufs(n, -1);
// 局部找根函数（带路径压缩，两趟法）
auto findRoot = [&ufs](int x) -> int
{
int child = x; // 记起点
while (ufs[x] >= 0) x = ufs[x]; // 爬到根
int root = x;
while (ufs[child] >= 0) // 沿原路压缩
{
int p = ufs[child];
ufs[child] = root;
child = p;
}
return root;
};
for (int i = 0; i < n; ++i) // 只处理右上三角即可
{
for (int j = i + 1; j < n; ++j) // 跳过 i==j 与左下镜像
{
if (isConnected[i][j] == 1) // i、j 直达
{
int r1 = findRoot(i); // 找 i 的根
int r2 = findRoot(j); // 找 j 的根
if (r1 != r2) // 不同省才合并
{
ufs[r1] += ufs[r2]; // 人数累加（负数相加）
ufs[r2] = r1; // r2 挂到 r1 下
}
}
}
}
int cnt = 0; // 统计根的数量
for (auto e : ufs) // 负数即根
if (e < 0) ++cnt;
return cnt; // 返回省份数
}
int main()
{
// 0 连 1，1 连 2：3 城连成一片，3 单独，共 2 个省份
std::vector<std::vector<int>> g = {
{1, 1, 0, 0},
{1, 1, 1, 0},
{0, 1, 1, 0},
{0, 0, 0, 1}
};
std::cout << "省份数量: " << findCircleNum(g) << std::endl; // 输出 2
return 0;
}这道题你在各大平台的同义变形："省份数量"（连通分量计数）——凡是要"数一数有几坨彼此互不连通的团块"的问题，几乎都能套这一套模板：遍历边、Union、数根。
应用二：等式方程的可满足性
再上一个稍微绕点的：给你一堆形如 "a==b" 或 "a!=b" 的等式，问它们能不能同时成立（可满足）。比如 a==b, b==c, a!=c 就是矛盾的。
思路分两遍走，课件里也写得明明白白：
- 第一遍，把所有
==两端的变量 Union 进同一个集合。a==b意味着 a 和 b 必须同属一个集合。 - 第二遍，逐个检查
!=两端的变量：如果它们竟然已经在同一个集合，说明x!=y和前面的相等关系冲突，直接判定不可满足。
因为变量都是单个小写字母，我们把它映射到 0~25 这 26 个下标，用一个长度 26 的数组当并查集即可。
#include <iostream>
#include <vector>
#include <string>
// 判断一组等式是否可同时满足
bool equationsPossible(std::vector<std::string>& equations)
{
std::vector<int> ufs(26, -1); // 26 个字母各是一组
// 找根（带压缩的 lambda）
auto findRoot = [&ufs](int x) -> int
{
int child = x;
while (ufs[x] >= 0) x = ufs[x];
int root = x;
while (ufs[child] >= 0)
{
int p = ufs[child];
ufs[child] = root;
child = p;
}
return root;
};
// 第一遍：先处理所有的 "=="，把相等的字母合并
for (auto& s : equations)
{
if (s[1] == '=') // 形如 "a==b"，s[0]=a, s[3]=b
{
int r1 = findRoot(s[0] - 'a'); // a 映射到下标
int r2 = findRoot(s[3] - 'a'); // b 映射到下标
if (r1 != r2)
{
ufs[r1] += ufs[r2]; // 合并
ufs[r2] = r1;
}
}
}
// 第二遍：凡是 "!="，若两端在同一集合则矛盾
for (auto& s : equations)
{
if (s[1] == '!') // 形如 "a!=b"
{
int r1 = findRoot(s[0] - 'a');
int r2 = findRoot(s[3] - 'a');
if (r1 == r2) // 相等关系已把它们绑一起
return false; // 与不等矛盾，不可满足
}
}
return true; // 全部通过，可满足
}
int main()
{
std::vector<std::string> e1 = {"a==b", "b==c", "a!=c"}; // 矛盾
std::vector<std::string> e2 = {"a==b", "b==c", "c==d"}; // 相容（无 !）
std::cout << "e1: " << (equationsPossible(e1) ? "可满足" : "矛盾")
<< std::endl; // 矛盾
std::cout << "e2: " << (equationsPossible(e2) ? "可满足" : "矛盾")
<< std::endl; // 可满足
return 0;
}这里有两个很典型的小坑，值得单独敲黑板。第一，为什么分成两遍而不是一遍处理完？因为"合并类操作必须在检查类操作之前全部完成"——如果边合并边检查，后面新加的 == 并集可能会"推翻"前面已下的 != 结论，顺序一乱就错，所以必须先 == 后 !=。第二，!= 的处理可以"提前结束"：只要发现某一对 != 两端的变量已经在同一集合，矛盾确定，立刻 return false，无需再看剩下的等式。
应用三：Kruskal 最小生成树（简单预告）
并查集还有一个压轴大用场——Kruskal 求最小生成树（MST）。这里给你一个大纲式的预告而不展开全实现，因为它本身够单独开一篇。思想是这样的：
把图里所有边按权重从小到大排序，然后从小到大一条条处理：对每条边
(u, v, w)，如果u和v当前不在同一个集合（加入这条边不会成环），就用并查集把它们 Union，并把这条边计入最小生成树；如果已经在同一集合，加进来会形成环，直接跳过。处理到选了顶点数 - 1条边为止，就得到一棵最小生成树。
发现没有，并查集在整个算法里扮演的唯一角色，就是快速判断"加这条边会不会成环"——这本质上就是 IsConnected(u, v)，一次 O(α(n)) 的查询，加上一次 O(1) 的 Union。把这张复用封装进前面那个 union_find 类，Kruskal 的主循环就极其清爽。这也是并查集被称为"图论里的万能胶"的原因之一。
边界、坑与避雷指南
并查集看起来短，但坑都藏在不显眼的地方。我把最常见的几条集中给你，你写的时候逐条核对，能少走很多弯路：
坑一：合并前必须重新找根，而不是直接用传入的下标当根。 传入的 x1, x2 只是普通元素编号，它们本人不一定是根。如果跳过 FindRoot 直接拿 x1 当数组下标去更新，很可能会把一个"挂在别人下面的元素"当成了根，把树搞乱甚至覆盖掉真实根的人数。所以 Union 里的第一件事永远是两个 FindRoot。这是新手最常犯的第一个错。
坑二：根的下标恰好在合并中被改写。 假设某次合并后 root2 的位置被改成了 root1，那下次再有人 FindRoot 到原来的 root2 时，它会先跳到 root1，再判断 root1 是不是根——逻辑是自洽的，因为你存的本就是"父亲下标"。但千万别在更新人数时用错了格子：_ufs[root1] += _ufs[root2]; _ufs[root2] = root1; 的先后顺序是固定的，先累加人数、后改指向，你要是写反了，先改指向再加，_ufs[root2] 已经是正数，累加的就是个错误的非负值，集合计数和大小全乱。一句话：先记账、后搬家。
坑三：按秩合并里的负号方向。 因为我们用负数存集合大小，"人多人少"的比较符号是反的：_ufs[root1] > _ufs[root2] 意味着 root1 人更少。很多人照抄"正数世界的思维"（< 才交换）导致总把大树挂到小树下，树越挂越高。每次核对排序逻辑，最好举个具体负数例子心算一遍。
坑四：秩的更新只发生在根的格子上。 合并更新的是 _ufs[root]、_ufs[root2] 这两个当下为根的下标。不要幻想去更新集合里其他成员的"秩"，它们根本不需要——只要查归属先 FindRoot 到根，根上的信息总是最新的。这也是并查集能保持 O(α(n)) 的关键：所有"账本"都记在根上。
坑五：路径压缩的触发时机。 压缩发生在 FindRoot 执行时，而不是发生在 Union 里。如果你只在少数几个元素上反复 FindRoot，那么树上其他分支并不会被压缩，这是正常的、也是符合预期的。想全局变"矮"，靠的就是大量 FindRoot 和 Union 摊还出来的总收益。不要在没见过 Count()/IsConnected 调用的前提下，指望树自动就被压平。
坑六：下标从 1 开始（而非 0）。 很多题目里顶点编号是 1..n 而不是 0..n-1。处理办法两类：要么把数组开成 n+1 个元素、直接让下标 0 闲置、用 1..n 当真实下标；要么在输入时全部减一、转成 0 基。千万不要开成 n 个却去访问下标 n，那会越界。若题目规定编号从 1 起，我建议直接开 size = n + 1，省心不混乱。
坑七：Union 返回 bool 的语义。 它返回的是"这次是否真的把两个集合合并了"，而不是"两个元素是否连通"。已连通时返回 false 是有用的信号——比如 Kruskal 里 "该边会成环、应跳过" 就可以用它来判断。别只看返回值就误判连通关系，先建树：连通性查询用 IsConnected，合并是否发生用 Union 的返回值。
坑八：栈溢出（递归 find 的隐患）。 递归版 FindRootRecursive 在把数组中元素全部顺序合并、"倒霉地对准"长链时，递归深度可能达到 O(n)，n 到几百万就可能爆栈。比赛/工程里优先用非递归两趟版，或者锻炼心智时用递归版也记得这是风险点。
坑九：泛型与下标类型。 我们一直用 int 当下标和存父亲。若 n 可能超过 int 范围（理论上大到天荒），要留意类型放大为 size_t 或 long long。实践中数组本身受内存限制，int 通常够用，但写通用类时在成员上别用错 size_t 与 int 的混搭比较（有无符号比较的坑）。
思考题：把知识嚼碎（含详细答案）
下面这几道题，是为了让你把"看得懂"变成"闭眼能写"。每题我都给了详细答案，先自己花两分钟想，再对照答案看自己漏了什么。
思考题一：初始 6 个元素（下标 0~5）都自成一集合，依次执行：Union(0,1)、Union(3,4)、Union(1,3)。问：此刻 Count() 是多少？IsConnected(0,4) 是 true 吗？请逐步推演数组形态。
答案：初始数组全 -1。Union(0,1)：根 0 与根 1 不同，人一样多（都是 1 人），比较 _ufs[0](-1) > _ufs[1](-1) 不成立，不交换，所以 root1=0 当新根：_ufs[0] = -1 + (-1) = -2，_ufs[1] = 0。Union(3,4)：同理 root1=3：_ufs[3] = -2，_ufs[4] = 3。Union(1,3)：FindRoot(1) 一路爬到 0（压缩后挂到 0），FindRoot(3) 是 3；0 与 3 不同；_ufs[0]=-2、_ufs[3]=-2，_ufs[0] > _ufs[3] 即 -2 > -2 不成立，不交换，root1=0 当根：_ufs[0] = -2 + (-2) = -4，_ufs[3] = 0。于是 Count() 数负数：_ufs 为 -4, 0, -1, 0, 3, -1，负数的下标是 0、2、5，共 3 个集合。IsConnected(0,4)：FindRoot(0)=0，FindRoot(4)=3→...→0，两者相等，为 true。要点：注意 Union(1,3) 时先找根得到 0 和 3，再比较负权决定谁当根。
思考题二：不用写代码，光靠脑内推演：Union 里 _ufs[root1] = root2; _ufs[root2] += _ufs[root1]; 这两行如果顺序颠倒，会出什么问题？用一个具体例子说明。
答案：以 root1 队 4 人、root2 队 3 人为例，正确顺序应先 _ufs[root1] += _ufs[root2]（把 3 并入 4，得 -7），再 _ufs[root2] = root1（root2 挂到 root1 下）。若颠倒：先 _ufs[root1] = root2——这时把 root1 的格子改成了正数 root2，root1 不再是根；再执行 _ufs[root2] += _ufs[root1]——试图累加 root1 的人数，可此刻 _ufs[root1] 已经被写成正数 root2（比如是 5），你累加的是 -3 + 5 = 2 这样的正数，既把 root2 的人数算成了个正数（破坏了"负数为根"的约定），又丢掉了 root1 那 4 人的人数。于是集合大小信息彻底损坏，Count() 也会数错。所以说：先记账、后搬家，顺序不能错。
思考题三：为什么路径压缩必须"回溯/第二趟"才能把链全压扁，而不能只在第一遍爬到根时把它压一次？
答案：第一遍 while (_ufs[index] >= 0) index = _ufs[index]; 结束时，index 已经移动到根上，原始起点和中间结点的下标都已经丢失了（除了我们用 child 额外存了起点）。如果你只在这一趟里"压"，你只压得到当前这个结点，而这时的当前结点已经是根、无从压起。要想把整条祖先链都改成直指根，必须要么回溯（递归版在回程时逐层改）、要么重走一遍原路（非递归版第二趟用 child 沿路径重走，每步把父亲信息用 parent 暂存再推进）。它揭示的通用心法是：路径压缩是"回溯型"操作，天然要求和原路对称的第二次访问，递归的调用栈或非递归的显式暂存都是在提供一个"回头路可以走"的载体。
思考题四：如果只做按秩合并、不做路径压缩，最坏复杂度是多少？只做路径压缩、不按秩合并呢？为什么两者缺一不可？
答案：只按秩合并的并查集，因为每次都是小树挂大树，单棵树高度始终被限制在 O(log n)，所以单次 FindRoot 最坏 O(log n)，总 O(m log n)。只做路径压缩而不用按秩合并，理论上存在刻意构造的病态序列（不断 Union 形成又高又瘦的结构，而偏偏从不触发压缩的那些路径），会让总代价退化到 O(m log n) 甚至更高的级别（经典教材能构造出接近这一上界的例子）。两者叠加才是 O(m α(n))：按秩合并把"最坏树高"压住，路径压缩把"实际开销"进一步摊薄，两者的势能相互补偿，才得到那个几乎等于常数的反阿克曼上界。所以工程判断是——两个都用，才能安心说自己写的是标准并查集。
思考题五：省份数量那题，为什么内层只遍历 j = i+1 而不遍历整个 j?
答案：因为 isConnected 是对称矩阵（图是"无向"的：i 连 j 必然 j 连 i），isConnected[i][j] 和 isConnected[j][i] 一定相等。若 i、j 都全量遍历，边 (i,j) 会被处理两遍，虽然并查集天然幂等（第二次发现已连通返回 false），不算错，但白白多做一半工作、多触发若干次 FindRoot。只用右上三角（j>i）+ 跳过对角线（j==i，自己连自己不产生新信息），在不损失任何一条边的前提下把遍历量减半。这是图题里很常见的对称性剪枝小技巧。
总结：一口气串起来
我们来把这一路收个尾。并查集用一个一维数组就完成了"负号=根、正数=父亲"的树形编码，从而把"查归属、判同类、合并、计数"四件事全部变成数组上的常数级小操作。它最精髓的两件神装是：路径压缩（FindRoot 顺手把沿途结点全部拍平到根下）与按秩合并（合并时让小树挂大树的根），两者合力把复杂度压到了近似的 O(α(n))——反阿克曼函数小到在实际数据量下就是"常量"。它的应用从最简单的连通分量计数（省份数量、朋友圈），到处理"==/!="约束可满足性，再到图论里大名鼎鼎的 Kruskal 最小生成树，处处都是它的身影。
最后再送你一句生活化心法，和红黑树那次不一样，并查集特别简单："谁跟谁是一伙的，就让他们认同一个老大；查的时候顺便把小队全员拉直挂到老大名下。" 抓住"找根即归队、压缩即拉直、合并看胖瘦"这三板斧，并查集你就算真的拿下了。
把文章里那份 union_find 完整类复制去编译跑一跑，再用"省份数量"和"等式可满足性"两个 demo 练手，你就从"看得懂"正式跨进了"写得出"的关口。下节课，我们可能要去看它能配合的邻居数据结构，或者把它拆开去研究它背后更精妙的势能分析——无论如何，这把"万能胶"，你已经焊进手里了。
还没有评论 — 第一条由你来留。