POJ1703(Find them, Catch them)--并查集

题目链接：http://poj.org/problem?id=1703

塔都市的警察局决定以混乱为目标，作为启动行动，扎根城市中的两个帮派，Gang Dragon和Gang Snake。 但是，警方首先需要确定犯罪分子属于哪个团伙。目前的问题是，两名罪犯; 他们属于同一个氏族吗？ 您必须根据不完整的信息做出判断。（因为歹徒总是暗中行动。） 假设N（N <= 10 ^ 5）罪犯目前在塔都市，编号从1到N.当然，他们中至少有一人属于Gang Dragon， 同样为Gang Snake。您将按顺序给出M（M <= 10 ^ 5）个消息，它们分为以下两种： 1。D [a] [b] 其中[a]和[b]是两个罪犯的数字，以及他们属于不同的帮派。 2. A [a] [b] 其中[a]和[b]是两个罪犯的数量。这需要您决定a和b是否属于同一个团伙。 输入 输入的第一行包含单个整数T（1 <= T <= 20），即测试用例的数量。然后是T案例。 每个测试用例以具有两个整数N和M的行开始，接着是M行，每行包含如上所述的一个消息。 产量 对于每种情况下的每条消息“A [a] [b]”，您的程序应根据之前获得的信息进行判断。 样本输入 1 5 5 A 1 2 D 1 2 A 1 2 D 2 4 A 1 4 样本输出 Not sure yet. In different gangs. In the same gang. 这个题目也是典型的并查集的题目,因为总共只有两个黑帮，所以可以用两个集合来求解。当让，用一个集合也可以。 只是要对relation进行细心设置(可以设置relatiin：0表示关系相同，1为关系不同)。在对一个元素执行Find（）操作时，如果它与父亲结点realtion相同，父亲结点与根结点relation相同，那么该元素与根结点关系也相同。否则是不同的。

 1 int DisJoinSet ::Find(int x)
 2 {
 3     int temp = tree[x].parent;//temp x的父亲结点
 4     if(x != tree[x].parent)
 5     {
 6         tree[x].parent = Find(tree[x].parent);//递归在双亲中找x
 7     // tree[temp].relation必为temp结点（x的父节点）与根节点的关系，tree[x].relation最初为x与temp的关系，
 8     // tree[x].relation == tree[temp].relation意味着tree[x].relation和tree[temp].relation同为1，或者同为0
 9     // 如果tree[x].relation和tree[temp].relation同为1，意味着根节点与temp不同类，temp与x不同类，总共只有2个集合，x与根节点必定同类。
10     // 如果tree[x].relation和tree[temp].relation同为0，意味着根节点与temp同类，temp与x同类，x与根节点也必定同类。
11         if(tree[x].relation == tree[temp].relation)
12         {
13             tree[x].relation = 0;
14         }
15     // tree[x].relation != tree[temp].relation意味着tree[x].relation和tree[temp].relation一个为1，一个为0，
16     // 如果tree[temp].relation为false，tree[temp].relation为1，意味着根节点和temp同类，temp与x不同类，那么x与根节点必然不同类
17     // 如果tree[temp].relation为true，tree[x].relation为0，意味着根节点和temp不同类，temp与x同类，那么x与根节点必然不同类
18         else
19         {
20             tree[x].relation = 1;
21         }    
22         return tree[x].parent;// 返回根节点下标
23     }
24     else
25     {
26         return x;
27     }
28 }

在进行合并操作时，因为合并的x和y是属于不同集合的，所以和上面一样的推理。

 1 void DisJoinSet ::Union(int x,int y)
 2 {
 3     int rootx = Find(x);
 4     int rooty = Find(y);
 5     if(rootx == rooty)
 6     {
 7         return ;
 8     }
 9     if(tree[rootx].rank > tree[rooty].rank)
10     {
11         tree[rooty].parent = rootx;
12         // 此时rooty与其根结点rootx的关系如何确定？因为Find方法也在进行路径压缩，x的父节点是rootx，y的父节点的rooty
13         // 如果tree[x].relation和tree[y].relation均为1，说明x和rootx不同类，y和rooty不同类，而已知x和y不同类，因此rooty和rootx不同类；
14         // 如果tree[x].relation和tree[y].relation均为0，说明x和rootx同类，y和rooty同类，而已知x和y不同类，因此rooty和rootx不同类
15         if(tree[x].relation == tree[y].relation)
16         {
17             tree[rooty].relation = 1;
18         }
19         // 如果tree[x].relation为1，tree[y].relation为0，说明x和rootx不同类，y和rooty同类，而已知x和y不同类，因此rooty和rootx必同类；
20         // 如果tree[x].relation为0，tree[y].relation为1，说明x和rootx同类，y和rooty不同类，而已知x和y不同类，因此rooty和rootx必同类；
21         else
22         {
23             tree[rooty].relation = 0;
24         }
25     }
26     else
27     {
28         tree[rootx].parent = rooty;
29         if(tree[rootx].rank == tree[rooty].rank)
30         {
31             tree[rooty].rank ++;
32         }
33         // 此时rooty与其根结点rootx的关系如何确定？因为Find方法也在进行路径压缩，x的父节点是rootx，y的父节点的rooty
34         // 如果relation[x]和relation[y]均为true，说明x和rootx不同类，y和rooty不同类，而已知x和y不同类，因此rooty和rootx不同类；
35         // 如果relation[x]和relation[y]均为false，说明x和rootx同类，y和rooty同类，而已知x和y不同类，因此rooty和rootx不同类
36         if(tree[x].relation == tree[y].relation)
37         {
38             tree[rootx].relation = 1;
39         }
40         // 如果tree[x].relation为1，tree[y].relation为0，说明x和rootx不同类，y和rooty同类，而已知x和y不同类，因此rooty和rootx必同类；
41         // 如果tree[x].relation为0，tree[y].relation为1，说明x和rootx同类，y和rooty不同类，而已知x和y不同类，因此rooty和rootx必同类；
42         else
43         {
44             tree[rootx].relation = 0;
45         }
46     }
47 }

完整代码：

  1 #include
  2 #include
  3 #include
  4 #include
  5 #include
  6 #include
  7 #include