【題意】：
有n個黑幫團伙成員，且有兩個幫派 。
D x y 表示 x y屬于不同的幫派；
A x y 詢問 x y的關系。
關系有三種：1.Not sure yet. 2.In different gangs. 3.In the same gangs.
給出m個操作，回答所有詢問。
【題解】：并查集題目，可是想不出來，給隊友點明了。
對于每個人，拆點x x’。
對于D x y這個操作,把x和y’所在的分量合并，x’和y所在的分量合并。
對于A x y這個詢問,
如果find(x) == find(y)，則他們屬于同一個幫派；
否則，如果find(x) == find(y')，他們屬于不同幫派；
否則，他們的關系不確定。
最好在紙上畫下圖，這樣比較容易理解。
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define maxn 200050
19 int n, m;
20 int fa[maxn];
21
22 void init() {
23 for(int i = 0; i < maxn; i++) fa[i] = i;
24 }
25
26 int find(int x) {
27 if(x != fa[x]) return fa[x] = find(fa[x]);
28 return fa[x];
29 }
30
31 bool un(int a, int b) {
32 a = find(a), b = find(b);
33 if(a == b) return false;
34 fa[a] = b;
35 return true;
36 }
37
38 int main() {
39 int T, a, b;
40 char op[5];
41 scanf("%d", &T);
42 while(T--) {
43 init();
44 scanf("%d%d", &n, &m);
45 for(int i = 0; i < m; i++) {
46 scanf("%s%d%d", op, &a, &b);
47 if(op[0] == 'A') {
48 if(find(a) == find(b)) printf("In the same gang.\n");
49 else if(find(a) == find(b+n)) printf("In different gangs.\n");
50 else printf("Not sure yet.\n");
51 } else {
52 un(a, b + n), un(a + n, b);
53 }
54 }
55 }
56 return 0;
57 }
58