训练4　帮派

题目描述（POJ1703）：警察局决定从两个帮派青龙帮和白蛇帮开始治理混乱，首先需要确定犯罪分子属于哪个团伙。比如，有两名罪犯，他们是否属于同一帮派？警察必须根据不完整的信息做出判断，因为歹徒总是暗中行动的。假设有N（N≤105）个罪犯，编号为1～N，其中至少有一人属于青龙帮，至少有一人属于白蛇帮，请依次给出M（M≤105）个消息，消息类型有两种：D a b，表示a和b属于不同的帮派；A a b，表示查询a和b是否属于同一帮派。

输入：第1行包含单个整数T（1≤T≤20），即测试用例的数量。每个测试用例都以两个整数N和M开始；接着是M行，每行都包含如上所述的一个消息。

输出：对每一个查询操作，都根据之前获得的信息进行判断，答案可能是In the same gangs、In the different gangs和Not sure yet，分别表示在同一帮派中、在不同的帮派中和还不确定。

题解：可以用一个集合表示一个帮派，根据集合号判定是否属于同一帮派。在并查集的基本操作中，Union(x, y)表示将x、y合并为同一个集合。与并查集的集合合并不同，本题要求将两者划分为不同的集合，该怎么办呢？

（1）划分为不同集合的方法：可以给每个节点x都复制一个影子x+n，将x、y划分为不同的集合，只需将x和y的影子（y+n）合并为同一集合，并将x的影子（x+n）和y合并为同一集合。执行Union(x, y+n)、Union(x+n, y)，表示x、y属于不同的集合。

（2）判定是否属于同一集合：因为将x、y划分为不同的集合时，与彼此的影子进行了合并，即x和y的影子（y+n）集合号相等或者x的影子（x+n）和y集合号相等时，说明x、y属于不同的集合；而x和y集合号相等或者x的影子（x+n）和y的影子（y+n）集合号相等时，说明x、y属于同一集合；对于其他情况，不确定其是否属于同一集合。

（3）合并优化：若将高树合并到矮树之下，则合并后的树高增1；若将矮树合并到高树之下，则合并后的树高不变。树高越大，查找祖宗时经过的节点越多，效率越低。因此采用启发式合并，将矮树合并到高树之下，若树的高度一样，则合并后树根的高度增1。

1. 算法设计

（1）初始化。将n扩大为2n个节点，初始化每个节点的集合号都为其自身，高度为0。

（2）划分为不同的集合。执行Union(x, y+n)、Union(x+n, y)，表示x、y属于不同的集合。

（3）判定是否属于同一集合。若(Find(y+n)==Find(x)||Find(x+n)==Find(y))，则属于不同的集合；若(Find(x)==Find(y)||Find(x+n)==Find(y+n))，则属于同一集合；否则不确定是否属于同一集合。

2. 完美图解

根据输入样例，求解过程如下。

（1）初始化。根据样例，一共有5个节点，将其扩大为10个节点。初始化每个节点的集合号都为其自身，高度h为0。

（2）A 1 2：查询1和2是否属于同一帮派。Find(1)=1，Find(6)=6，Find(2)=2，Find(7)=7，前两个判定条件均不满足，不确定1和2是否属于同一帮派。

（3）D 1 2：将1和2划分为不同的集合。将1和2+5合并，将1+5和2合并。

（4）A 1 2：查询1和2是否属于同一帮派。因为(Find(2+5)==Find(1)||Find(1+5)==Find(2))，所以1和2不属于同一帮派。

（5）D 2 4：将2和4划分为不同的集合。可以将2和4+5合并，将2+5和4合并。将高度小的树合并到高度大的树下面，因此将9合并到2下面，将4合并到7下面。

（6）A 1 4：表示查询1和4是否属于同一帮派。因为(Find(1)==Find(4)||Find(1+5)==Find(4+5))，所以1和4属于同一帮派。

3. 算法实现

（1）初始化。初始化每个节点的集合号为其自身，高度为0。

（2）查找集合号。与在并查集中查找集合号的方法一样。

（3）划分为不同的集合。将x、y划分为不同的集合，分为两个步骤：①Union(x, y+n)，②Union (x+n, y)。Union()操作与并查集的合并方法一致，这里只是做了合并优化，把矮树合并到高树之下，若树的高度一样，则合并后树根的高度增1。

（4）判定结果。若划分不同的集合，则执行Union(x, y+n)、Union(x+n, y)。若判定结果，则根据3个判定条件输出答案即可。