POJ1703 Find them, Catch them

并查集。

这题更加深了对并查集的理解，以前做过差不多的类似“朋友传递”的题。这道题核心的一句话是：敌人的敌人是朋友。那么假设每个x总有一个敌人（编号为x+n），那么可以把a加入到b的敌人b+n代表的并查集中，把b加入到a的敌人a+n的并查集中。如果find(a)==find(b)，那么a和b是同gang；如果find(a)==find(b+n)或者find(b)==find(a+n)，那么a和b是不同的gangs；否则，not sure。

View Code

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #define M 100010
 5 using namespace std;
 6 int f[M << 1];
 7 
 8 int find(int x)
 9 {
10     return x == f[x] ? f[x] : f[x] = find(f[x]);
11 }
12 
13 int main()
14 {
15     int T, m, a, b, n;
16     char cmd[3];
17     scanf("%d", &T);
18     while (T --)
19     {
20         scanf("%d%d", &n, &m);
21         for (int i = 0; i <= 2 * n; i++)
22             f[i] = i;
23         while (m--)
24         {
25             scanf("%s%d%d", cmd, &a, &b);
26             if (cmd[0] == 'D')
27             {
28                 f[find(a)] = find(b + n);
29                 f[find(b)] = find(a + n);
30             }
31             else
32             {
33                 if(find(a) == find(b))
34                     puts("In the same gang.");
35                 else if(find(a) == find(b + n) || find(a + n) == find(b))
36                     puts("In different gangs.");
37                 else
38                     puts("Not sure yet.");
39             }
40         }
41     }
42     return 0;
43 }