反向并查集

并查集主要处理的是元素之间合并与查询的问题。合并,实际上就是连边的过程,这对于并查集来说是最基础也是最重要的操作;但是对于合并的逆操作,也就是断开某两个元素之间的联系,是一件比较困难的事,这里,就用到了反向并查集。

断开联系可以通过断开两个点之间的边或者是直接移除某个点来完成,而后者的本质就相当于是断开与这个点相连的所有边。下面举两个常见的题型背景。

1、有一个国家有 n 个城市,在这些城市中有 m 条路,这些路是这样给出的:“起点城市编号 终点城市编号”。然后现在要拆掉一些路,按拆除顺序给出,格式与上述一致,问你在每拆完一条路之后,国家被分成了多少个部分。

2、有一个根据地有 n 个小组,其中有 m 对联系,“小组标号1 小组标号2”代表小组1和小组2有联系。只要可以直接或间接建立联系,那么这若干个小组就被称为一个团队,现在陆续有一些小组被敌人消灭了,问你每当一个小组被消灭后,剩余的小组可以组成多少个团队。

总的来说,这两道题的核心都是在问断掉一些联系之后还有多少个连通分量。对于这一类题目,我们可以通过反向合并,也就是按照断边顺序的反序进行连边。在这个过程之前,我们需要先把那些没有受到断边影响的边全部连上,连边时根据合并集合的数量进行接下来的操作。

在第一个例子中,我们可以使用map<pair<int,int>,bool>来标记所有的边,如果某条边是要被拆除的,就把它标为false,其余标为true,标记完成后,遍历这个map,把所有标为true的边全部连上,此时统计一下集合的数量,这个数量即为拆除最后一条边后,国家被分成的部分。准备工作做好了,接下里我们只需要从最后一个拆除的边往前遍历,每连一条边,就看这条边是否把两个集合连在了一起,如果有集合数减一,如果没有集合数不变,最后反向输出答案即可。

在第二个例子中,我们需要先使用vector<int>vec[maxn]把所有边之间的联系全部保存下来,然后开一个数组标记那些被消灭掉的小组。这时遍历vec[maxn],把那些没有被消灭的小组之间的联系全部建立起来,此时记录一下集合的数量,这个数量就是最后一个小组被消灭之后团队的数量。接下来只需要从最后一个被消灭的小组往前遍历,每恢复一个小组,我们就把这个小组标为未消灭(注意,这里用的还是上文中提到的那个数组),然后把这个小组与其他未被消灭的小组之间的联系建立起来,假设这个小组最后把 cnt 个集合并在了一起,那么集合数就减少 cnt – 1,这里需要注意的是,如果这个小组没有合并任何一个(包括自己)集合,那么 cnt 就为 0,集合数减少 (0 – 1) 个,也就是增加一个,这是没有问题的。最后同样是反向输出答案。

为什么可以通过反向并查集来处理断边问题呢?假设一个断边序列:a、b、c。我们首先会恢复除a、b、c这三条边以外的其他边(这里虽然没什么差别,但还是把过程写在这里),然后恢复 c 边的时候,我们没有考虑边 a 和边 b(因为此时 a 和 b还尚未恢复),恢复 b 边的时候,没有考虑 a 而考虑了 c。综合我们断边的例子想一下这个问题,我们在断掉 b 边的时候,a 边已经在之前被断掉了,所以我们断掉 b 边时只会对在 b 之后的断掉的边有影响,而对于在 b 边之前已经被断掉的边没有任何关系。

给出几道例题:

1、Connections in Galaxy War

2、红色警报

3、刘学习的会模糊的卡诺图

当然这种反向并查集的题还有很多,我只给了几道有代表性且具有一定难度的题。