1. 标准并查集不敢碰的问题怎么表示不同类先从我自己的经历说起。最早学并查集的时候我以为把同一个团伙的人往一棵树上 merge 就完事了直到做题碰到敌人的敌人是朋友我愣住了两个人互相敌对我到底该把谁合并到谁合并了就成朋友了不合并又丢了这条敌对关系。那段时间我把并查集模板背得滚瓜烂熟却始终回答不了这个简单的问题并查集能不能表达这两个东西一定不是同类答案是普通并查集不能。原因要从并查集的语义说起。merge(x, y)的底层含义是x 和 y 属于同一个等价类它天然带传递性x 和 y 同集y 和 z 同集那么 x 和 z 必然同集。这种语义用来表达朋友关系连通块群组成员是非常自然的因为这些都是等价关系。但敌对不是等价关系。如果我用merge(x, y)表示x 和 y 敌对那么由传递性会推出x 敌 yy 敌 z则 x 敌 z。这显然不对现实中 x 和 z 可能恰好是朋友甚至可能是一伙的。所以你不能把不是同类直接塞进普通并查集的合并操作里否则整个集合的结构会在不知不觉中变成一团互相矛盾的错误信息。换个说法普通并查集只关心两个元素之间有没有关系它不区分有关系但相反这种情况。而实际题目中我们遇到的关系往往不是简单的在一起而是必须在不同阵营一个是另一个的天敌。这时候你就需要一个能表达对立语义的并查集变体也就是标题里写的种类并查集在中文算法圈里更常见的叫法是反集。反集的思路非常直白既然普通并查集只能表达同属一个集合那我就把一个点拆成两个点一个表示这个点所在的阵营另一个表示这个点的对立阵营。这样原本用一条并查集无法表达的敌对关系就变成了一场普通的集合合并。下面我把这个模型拆开讲透。2. 反集的核心建模每个点拆成两个镜像反集的构建可以分两步先开一张双倍大小的并查集再重新定义每个下标的含义。2.1 一张双倍并查集里面存的是语义假设有 n 个实体编号从 1 到 n。反集的做法是开一个大小为 2n 的并查集然后下标i代表与 i 同类的整体可以理解为 i 所在阵营本身下标i n代表与 i 不同类的整体也就是 i 的敌对阵营。注意这里的阵营是抽象概念不是一个具体标签。比如两个监狱问题里你不需要知道 1 号犯人到底被分到 A 监狱还是 B 监狱你只需要知道他所在阵营的编号在并查集里是某个根结点而他的对立阵营也对应另一个根结点。反集不关心绝对阵营叫什么名字只关心相对关系。这样设计之后find(i)和find(j)相等就表示 i 和 j 在同一个阵营里find(i)和find(j n)相等就表示 i 和 j 处于不同阵营。你甚至可以在一张图上同时表达i 和 j 是朋友j 和 k 是敌人k 和 i 是朋友这样一串相对关系而不会产生逻辑混乱。这个模型的关键在于**原来的每个实体在反集里都有本体和镜像两个身份。**本体所在的集合代表它所属的阵营镜像所在的集合代表它不属于的那个阵营。题目里每给出一条关系我们要做的并不是找出谁是哪一类而是把对应的集合代表合并起来。2.2 两类关系的合并规则缺一条都不行如果 x 和 y 是同类朋友、同一监狱合并方式是// 同类关系 unit(x, y); unit(x n, y n);为什么要有第二条因为 x 和 y 同阵营的同时它们的对立阵营也应该合并成一个。如果不合并镜像那么后续如果有人查询(x 的敌人) 和 (y 的敌人) 是否为友时就会得到错误答案。同类关系的本质是两个维度同步合并本体跟本体反集跟反集。如果 x 和 y 是不同类敌人、必须在不同监狱合并方式是// 敌对关系两条都要写 unit(x, y n); unit(y, x n);这里很多人会漏掉第二行。敌对是对称关系x 的阵营等于 y 的对立阵营同时 y 的阵营也等于 x 的对立阵营。只写一边虽然能处理部分查询但一旦数据流经过反向路径并查集的信息就不完整了。我最开始在关押罪犯里只写了第一条合并样例全过提交却错查了半天才发现是这个问题。为了彻底理解为什么这两条 merge 能表达敌人的敌人是朋友可以做一个推演。假设 a 和 b 敌对b 和 c 敌对那么执行合并后a 和 b n 在同一集合b 和 c n 在同一集合b 和 a n 在同一集合c 和 b n 在同一集合。前两条合并意味着 b n 既和 a 同集又和 c 同集所以 a 和 c 必然在同一集合。这正是敌人的敌人是朋友的并查集证明。反集不需要你单独处理这种传递关系合并的自然结果就是对的。2.3 矛盾检测什么时候该说这条关系不成立在普通并查集里你几乎不需要判断矛盾因为所有关系合并起来都是一样的。但种类并查集里一个关系可能是假的判断标准是看它是否与已有的集合归属冲突。比如已知 x 和 y 是同类此时又来一条x 和 y 是敌人。在合并前先检查如果find(x) find(y)说明它们已经在同一阵营这和新关系不冲突因为同类如果find(x) find(y n)说明从已有信息能推出 x 必须和 y 敌对现在却说它们同类那就是矛盾如果find(y) find(x n)同理冲突。最标志性的矛盾是find(i) find(i n)。正常情况下一个实体的本体和镜像绝对不可能在同一集合里因为那意味着i 和它的敌人是一伙的。一旦出现这种情况说明前面的合并逻辑出错了或者题目输入给了一组无法满足的关系。我在调试反集题时经常在关键位置打一行assert(find(i) ! find(i n))很多隐蔽错误就会立刻浮出来。3. 三倍并查集食物链里的循环对立两倍反集能处理同类 vs 不同类但有些题目的对立关系不是二元的而是环形的。最典型的例子是食物链三种动物A 吃 BB 吃 CC 吃 A。注意这里 B 和 C 并不是简单的不同类因为不同类还分两个方向B 被 C 吃而 C 吃 B。如果你只用两倍反集只能表达B 和 C 敌对根本表达不了捕食方向这个信息。所以要用三倍并查集。把每个实体 i 拆成三个状态i表示 i 本身的阵营i n表示 i 的某种下一状态阵营i 2n表示 i 的下一状态的下一状态阵营。在食物链的常见解法里三个状态可以理解为某种循环编号状态 0 吃状态 1状态 1 吃状态 2状态 2 吃状态 0。这样一来一条x 吃 y的关系其实就是把 x 的状态 0 和 y 的状态 1 合并把 x 的状态 1 和 y 的状态 2 合并把 x 的状态 2 和 y 的状态 0 合并。三条合并是一个完整的轮换缺少任何一条都会破坏循环传递性。代码可以这样写// 同类三个状态分别合并 unit(x, y); unit(x n, y n); unit(x 2 * n, y 2 * n); // x 吃 y状态循环偏移 unit(x, y n); unit(x n, y 2 * n); unit(x 2 * n, y);判断一句话是否为假时要在合并之前检查如果说x 和 y 同类但find(x) find(y n)或find(x) find(y 2 * n)则矛盾如果说x 吃 y但find(x) find(y)同类或find(x n) find(y)说明 y 吃 x则矛盾。我见过不少人在写食物链时把自己绕晕原因就是把三个状态的顺序搞反了。我的建议是不要死记代码而是先在草稿纸上画三条横线每一行代表一个状态然后把 x 吃 y 写成一组斜向合并检查这组合并是否覆盖了所有三个状态。如果覆盖完整无论你选的方向和大多数人是否一样逻辑都是自洽的。方向本身不重要重要的是循环关系必须闭合。三倍并查集能解决的问题本质上还是种类数固定且关系是循环等价的模型。如果种类数再多一点比如 5 种动物围成一个圈互相吃理论上可以开 5n 的并查集继续做但实际题目很少见。更多情况下复杂关系会转向带权并查集这个我放在后面讲。4. 从两道经典题看反集怎么落地理解了反集的模型下面用两道最经典的题目把流程走一遍。这两道题几乎就是反集的代名词把它们的思路吃透其他同类题基本就是换皮。4.1 团伙朋友关系和敌人关系混合时该怎么合并题目大概是这样的有 n 个人告诉你一些朋友关系和敌人关系其中朋友的朋友是朋友敌人的敌人是朋友。问最多分成多少个团伙。这个题不需要知道每个人在哪个团伙只需要维护相对关系。所以直接用反集朋友unit(x, y)和unit(x n, y n)敌人unit(x, y n)和unit(y, x n)。处理完所有关系后统计 1 到 n 中有多少个不同的根结点答案就是团伙数。这个题最让我觉得反集神奇的地方是我自始至终不知道任何人属于哪个具体团伙但只要合并不漏最后数根的个数就是对的。这是因为反集保存的是阵营等价类的信息而不是阵营标签的信息。两倍并查集里有多个根结点每个根结点代表一个阵营类所有归属于同一阵营类的实体无论是本体还是某个实体的镜像都会被压缩到同一个根下。如果你第一次接触反集建议亲手把一个小数据跑一遍。比如 4 个人1 和 2 是朋友3 和 4 是敌人1 和 3 是敌人。合并完你会发现2 和 4 自动变成了朋友敌人的敌人是朋友这就是反集传递性的直观体现。4.2 关押罪犯贪心加反集的可行性判定关押罪犯是我个人觉得反集应用里最优雅的一道题。题面很经典有 n 个罪犯m 对仇恨关系每对关系有一个怨气值。要把所有人分到两个监狱问怎么分配能使得同一个监狱里的最大怨气值最小。这题的思考路径是反过来的。我们不是在合并阵营而是在不断尝试让一对人必须分到不同的阵营。于是可以按怨气值从大到小排序从最大怨气开始依次尝试满足这两人必须分开这个条件。如果某一条关系的两人已经在之前的约束下被迫进入同一阵营那么这条关系就无法满足它就成了必须存在的最大怨气值答案就是它。伪代码流程sort(edges, edges m, cmp); // 按怨气值从大到小 for (int i 0; i m; i) { int x edges[i].x; int y edges[i].y; if (find(x) find(y)) { ans edges[i].w; break; } unit(x, y n); unit(y, x n); }为什么这个贪心是对的因为一旦在某个权值 w 处无法满足x 和 y 不同监狱就说明在所有大于 w 的关系都被满足的条件下x 和 y 已经不可避免地瓜葛在了一起。你不可能通过后续的合并把这个事实拆开因为后续关系的权值只会更小而前面更大的怨气已经被满足了。所以 w 就是最优解的下限同时按这个分配方案w 也确实可以被实现。做这个题时一个容易踩的坑是忘记在判断冲突之前处理所有更大的边。如果你一边排序一边合并顺序错了前面的约束还没合并完就去判断当前边会出现把本来合法的方案判断成矛盾的情况。一定要等前面的关系全部合并完再对当前这条做find(x) find(y)的检查。4.3 什么时候该收手反集和带权并查集的分岔路反集虽然好用但它不是万能的。它解决的是关系对称、种类数少且关系是等价或循环等价的问题。一旦关系带上方向或者带上数值偏移就该换带权并查集了。比如有题目说a 比 b 大 3这种关系无法用同类/不同类来表达。你也许能开很多倍并查集去硬存所有可能的差值但差值范围一大就爆炸了。带权并查集的思路是让每个点记录自己到根结点的一个权值合并时对权值做运算。它可以表达a 比 b 大 3这种偏移关系典型应用包括区间和的校验、奇偶性问题等。做一个简单的对比表维度反集种类并查集带权并查集存储方式每个实体拆成 k 个虚点开 k 倍数组每个点记录到根的权值 d[x]关系类型同类/不同类、循环捕食带方向、带数值偏移的差分关系合并操作多次 unit 对应关系映射对权值做加减或模运算判断矛盾检查同类/异类是否同时成立检查权值运算是否与现有偏移冲突典型题目团伙、关押罪犯、食物链三倍奇偶校验、区间和、带权食物链要注意的是食物链这道题既可以用三倍反集也可以用带权并查集。用带权并查集时每个点维护一个值 mod 30 表示同类1 表示吃2 表示被吃。两种做法都能过差别只是思维方式不同。我个人更推荐先掌握反集因为它更符合人类直觉代码也不容易写错等反集熟练了再去看带权并查集你会发现带权版本本质上是在做同一种事情只是把多开几倍数组换成了给边加上权值。5. 我踩过的反集大坑初始化、合并方向与边界最后这部分是我刷了十几道反集题后攒下来的实战教训。很多错误看起来是玄学 WA实际上都是同一个套路。5.1 初始化只写了 1 到 n导致 find(x n) 得到垃圾值反集最基础也最致命的坑。代码里我习惯写for (int i 1; i n; i) fa[i] i;然后fa[x n]没初始化find(x n)返回的是 0 或者某个未定义的索引后续合并全乱套。正确做法是for (int i 1; i 2 * n; i) fa[i] i; // 两倍反集 // 三倍就写成 3 * n如果你发现程序在某些测试点随机 WA偶尔又 AC先检查初始化范围十有八九是这里出了问题。5.2 敌对的合并只写一半前面已经强调过这里再单独说一次。错误代码长这样unit(x, y n); // 漏掉 unit(y, x n);这个错误最阴险的地方在于它经常不会马上暴露。如果你的题目只在特定方向查询关系比如总是从更小的编号往更大的编号查那么漏掉反向合并也可能碰巧 AC。但一旦数据路径相反就会产生一个没有连通的集合导致某些本应推导出来的关系推不出来。调试方法很简单在所有敌对合并处打印 x、y人肉检查一下两个方向是否都执行了或者直接写成一个小函数封装避免手滑。5.3 同类关系合并后镜像侧没有同步很多人在处理朋友关系时写unit(x, y)就结束了忘了还有unit(x n, y n)。这样的后果是x 和 y 的正向阵营合并了但两个敌对阵营仍然是独立的后续任何涉及x 的敌人和y 的敌人的查询都会错。特别是当题目同时存在敌友关系时这种错误几乎必然导致答案偏大或偏小因为等价类的划分没有完整传递。5.4 没有检查 i 和 i n 是否被合并到一起当数据本身自相矛盾或者你的合并逻辑在某些路径下把本体和镜像连到同一棵树上时find(i) find(i n)会成立。这种状态代表着i 既属于自己阵营又属于敌对阵营整个模型已经没有意义了。如果你在调试过程中发现结果完全不可解释先在所有关键分支加一个断言if (find(x) find(x n) || find(y) find(y n)) { // 这里一定出事了 }能帮你快速定位是哪条合并惹的祸。5.5 食物链方向记错三倍并查集的轮换问题食物链的三倍并查集很多人栽在状态偏移方向上。正因为方向可以任意选择网上教程的写法甚至会互相矛盾你看三个博客可能有三种合并方式但它们可能都是对的。问题在于你只记住了代码没有记住循环轮换这个本质。一旦你混用了两套方向就会出现x 吃 y 合并时用了 A 方案z 吃 x 时用了 B 方案最后脑子里觉得逻辑没问题实际上三个状态的映射早就错乱了。我的建议是每次做食物链都自己在纸上把状态 0、1、2 写出来用一条x 吃 y的关系去验证三组合并是不是等距偏移。检查通过后把这一组合并复制成自己的模板以后不要再换方向。最后分享一个小技巧。我后来把反集的合并封装成一个关系映射函数比如mergeRelation(x, y, type)type 为 0 表示同类1 表示敌对2 表示循环捕食。这样在做陌生题目时我只需要对着题面确认每类关系对应哪种 type然后循环调用即可。自从用了这个封装少合并一次这种低级错误就从我的代码里彻底消失了。反集的逻辑本身并不难难的只是你在紧张写题时能不能保证每一步合并不漏、方向不错、范围开够。只要把以上几个坑全部避开种类并查集就是一套非常好用的工具。