团伙

【问题描述】

某地的黑社会组织猖獗，警方经过长期的调查，初步获得了一些资料：整个组织有 n 个人，任何两个认识的人不是朋友就是敌人，而且满足：① 朋友的朋友是朋友；② 敌人的敌人是朋友。

所有是朋友的人组成一个团伙。现在，警方拥有关于这 n 个人的 m 条信息（即某两个人是朋友，或某两个人是敌人），请你计算出该地最多可能有多少个团伙。

【分析】对于朋友信息，很容易想到用并查集进行集合合并。

对于敌人信息，我们也会想到并查集：如果3和5是敌人，他们应该在同一集合；接下来3和8成为敌人，也处在同一集合。这样，5和8就成为了朋友，同一集合内出现了两种关系——朋友、敌人。

为了解决这个问题，我们需要仔细分析一下。为了利用并查集，我们要统一关系：要么集合内都是朋友，要么都是敌人。通过上面的例子可以看出，集合内不能都是敌人。所以集合内应该都是朋友。

3和5为敌，就是3的敌人和5为朋友。我们不妨将3的敌人记作3'，那么8和3'也是朋友。同样，3 和5'、3和8'也是朋友。这样就可以用并查集表示敌人的关系了。

(3) 银河英雄传说

【问题描述】

银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。

杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1，2，…，30000。之后，他把自己的战舰也依次编号为1，2，…，

30000，让第i号战舰处于第 i 列(i＝1，2，…，30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为 “M i j”，含义为让第 i 号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第 j 号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。

在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：“C i j”。该指令意思是，询问电脑，杨威利的第 i 号战舰与第 j 号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。

【分析】

由于我们要得到的信息除了某条战舰在哪个队列，还要知道它在该队列中的位置。因此需要对并查集进行扩充。

原有的并查集可以得到parent、count，即战舰的父亲节点、战舰本身和它后面的战舰数量（仅在战舰的父节点是它本身时有意义）。可见，光有这两个数据是不能求出任意两艘战舰的战舰数量的。

设depth表示战舰到其父亲节点的战舰数量（包括父亲节点本身），即深度。

刚开始时，每个节点的parent是它自己，depth等于0，count等于1。

在回答“M i j”时，先对i、j进行查找和路径压缩，如果i、j的父亲f1、f2不相等，则进行合并：

令parent[f2]=f1，depth[f2]=count[f1]，count[f1]=count[f1]+count[f2]。

（此外，路径压缩时，如果结点a的最终的父亲是f，则需要令depth[a]+=depth[f]）

在回答“C i j”时，先进行查找和路径压缩。如果位于同一集合，则输出i、j的depth的差值减去1，否则输出-1。

(4) 可爱的猴子

【问题描述】树上挂着 n 只可爱的猴子，编号为1，…，n（2≤n≤200000)。猴子1的尾巴挂在树上，每只猴子有两只手，每只手可以最多抓住一只猴子的尾巴。所有的猴子都是悬空的，因此如果一旦脱离了树，猴子会立刻掉到地上。第0，1，…，m（1≤m≤400000）秒钟每一秒都有某个猴子把它的某只手松开，因此常常有猴子掉到地上。现在请你根据这些信息，计算出每个猴子掉在地上的时间。

【分析】

如果把连在一起的猴子看成一个集合，每次松手就是断开了集合之间的某些联系或者直接将一个集合分离成两个。

我们要求的是每只猴子第一次脱离猴子1所在集合的时间。

难道要用“分查集”来实现吗？

我们不妨反过来想，如果时间从第 m 秒开始倒流，则出现的情形就是不断有某只猴子的手抓住另一只猴子。

则我们要求的就转化成了：每只猴子最开始在什么时候合并到猴子1所在的集合。这样就可以应用并查集了。设在第 t 秒钟，猴子 i 抓住（实际上是放开）了猴子 j，那么此时就将 i 所在的集合与 j 所在的集合合并。

如果需要合并，并且原先猴子 i 与猴子 j 在同一个集合，那么就将猴子 j 所在集合的所有猴子掉落的时刻都设为 t。

为了枚举某一个集合里的所有元素，我们还需要用一个链表结构与并查集共同维护猴子的集合。