种类并查集


问题背景

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

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

例题:[NOIP2010 提高组] 关押罪犯

算法实现

基础实现

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

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

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

拓展

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

例如[NOI2001] 食物链

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

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

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

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

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

upd 20230710

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

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

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