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

1. 种类并查集

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

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

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

现在我们知道 2, 4 是敌人，那么 merge(2, 4 + n), merge(2 + n, 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. 实际例题

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

转载地址：https://memcpy0.blog.csdn.net/article/details/108287224 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！