种类并查集

发表于 2022-08-08 分类于信奥，算法阅读次数：

问题背景

并查集本来是很经典也很简单的数据结构，但是本蒟蒻当时学的时候是自学的，对于并查集的拓展是一窍不通，所以种类并查集什么的根本就不会。

那什么是种类并查集呢？并查集告诉我们：亲戚的亲戚是亲戚，而种类并查集可以告诉我们：敌人的敌人是朋友。也就是说，告诉你若干个对立关系，问某两个人是联合的还是对立的。

种类并查集的实现方法也很简单：把每个人拆成两个点，一个是“真身”，一个负责“接敌”。每当有一个对立关系的时候，就把a的“真身”和b的“接敌”连在一起，同时把b的“真身”和a的“接敌”连在一起。如下：

有什么用呢？先不急，我们再考虑b和c的对立关系：把c的“真身”和b的“接敌”连在一起，同时把b的“真身”和c的“接敌”连在一起。如下：

在查询的时候我们用真身查询。可以发现，a的真身和c的真身被b的接敌连在一起了！这样子，种类并查集就实现了“敌人的敌人是朋友”。

实际上来说，种类并查集并不仅限与2类，可以有多种不同的对立关系，只要每个人都多开一些节点就好了。

每一个动物都应该有3种状态：吃别人，被别人吃和真身（为了解决“同类”的输入）。

种类并查集还有一个应用：动态判断二分图。

在往图中加边的过程中，利用种类并查集可以动态判断是否为二分图（没有奇环的无向图）。

因为没有奇环，所以如果用两种颜色给二分图染色，相邻的节点颜色可以做到都不相同。基于这个性质，每加一条边，就相当于在两个节点中建立一种对立关系，可以用种类并查集来维护。如果在加边的过程中发现两个点已经在同一个集合里，那么就说明图不再是二分图。

在只加边不删边的情况下，一但变得不是二分图，就不可能再变回来了（此时并查集也已经不合法了）。

今天重新做了[NOI2001] 食物链，感觉之前说得很不清楚。

种类并查集并没有所谓“真身”的区别。三个不同的种类地位是相同的。在种类并查集中，将 \(i\) 的 A 和 \(j\) 的 B 相连的真正含义是：如果 \(i\) 的真实种类为 A，那么 \(j\) 的真实种类就是 B。反过来，\(j\) 是 B 则 \(i\) 就是 A。

这样应该更好理解一些。做这种题，首先要明确有哪些类别，比如：进第一个监狱的和进第二个监狱的；是动物 A 的与是动物 B 的。