本文共 900 字，大约阅读时间需要 3 分钟。

---

1. 种类并查集

如果说一般的并查集，维护的是等价、连通关系，例如朋友的朋友是朋友。那么种类并查集，维护的就是对立关系：敌人的敌人是朋友，或者更宽泛的说，是多个种类集合间的一种循环对称的关系。

常见的做法是将原并查集扩大一倍规模，并划分为两个种类。在同种类的并查集中合并，和原始的并查集没什么区别，仍然表达 他们是朋友 这个含义。在不同种类的并查集中进行合并，表达的则是 他们是敌人 这个含义。

例如，要维护 4 个元素的种类并查集，要开 8 个单位的空间：

用 1-4 维护朋友关系，5-8 维护敌人关系。如果我们现在知道 1, 2 是敌人，该怎样做呢？我们用新的 merge 函数，merge(1, 2 + n), merge(1 + n, 2); 。n 在这里等于 4 ，对于编号为 i 的元素，i + n 是它的敌人。于是这两句表示 1 是 2 的敌人，2 是 1 的敌人，如下图：

现在我们知道 2, 4 是敌人，那么 merge(2, 4 + n), merge(2 + n, 4); ：

于是，2, 4 是敌人，1, 2 是敌人。所以有敌人的敌人就是朋友， 1, 4 是朋友——通过 2 + n 这个元素将 1, 4 间接地连接起来了。1, 4 现在在同一个集合之中，表示它们是同一类人。

上述就是种类并查集的基本工作原理。我们把 1~n 看做是原本的并查集，n+1~2n 看做是表示敌对关系的并查集。

更复杂的看法是：将 1~n 看做同一类人 A ，n+1~2n 看做另一类人 B 。(1, 2), (2, 4) 是敌对关系，但是我们不知道它们分别是哪一类人，于是我们都做出尝试：A 中的 1, 2 分别和 B 中的 2, 4 敌对，B 中的 1, 2 分别和 A 中的 2, 4 敌对。

判断 1, 4 是不是朋友，只需看 A 中的 1 和 B 中的 4 、B 中的 1 和 A 中的 4 是否敌对（看两者之一就可以了）——很显然不敌对，于是是朋友。

---

2. 实际例题

为了实际掌握种类并查集的工作原理，我们需要做题：

：两个种类； ：两个种类； ：两个种类； ：三个种类；

转载地址：http://lxotf.baihongyu.com/