下载掌阅APP，畅读海量书库
立即打开
题目描述（POJ1703）： 警察局决定从两个帮派青龙帮和白蛇帮开始治理混乱，首先需要确定犯罪分子属于哪个团伙。比如，有两名罪犯，他们是否属于同一帮派？警察必须根据不完整的信息做出判断，因为歹徒总是暗中行动的。假设有 N （ N ≤10 5 ）个罪犯，编号为1～ N ，其中至少有一人属于青龙帮，至少有一人属于白蛇帮，请依次给出 M （ M ≤10 5 ）个消息，消息类型有两种：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）初始化。将 n 扩大为2 n 个节点，初始化每个节点的集合号都为其自身，高度为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 ))，则属于同一集合；否则不确定是否属于同一集合。
根据输入样例，求解过程如下。
（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属于同一帮派。
（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个判定条件输出答案即可。
