题意：是一个城市有两个帮派Gang Dragon 和 Gang Snake，A a b是询问a和b这两个人是不是一个帮派，D a b是这两个人不在一个帮派 每一次A就输出一次。
城市有只有3中人，要么属于S，要么属于D，还有一种未知
这题和奇偶游戏很相似，可以用扩展域并查集，也可以用边带权并查集，感觉扩展域更好写一些
扩展域：对于每个人x拆成x_d,x_s,分别表示x属于帮派D和帮派S，设x表示它属于帮派D，x+n表示属于S，那么对于每次询问D a b,a和b不同时属于一个集合，我们合并a_d和b_s,a_s和b_d，这说明它们是关联在一起的。
对于每次查询，我们如果a,b在一个集合中，说明他们属于同一派，如果a+n和b在同一个集合中说明他们不属于同一派，如果这两种都不满足，就是未知
#include#include using namespace std;const int N = 2e5 + 10;int fa[N],t,n,m;int get(int x){ if (fa[x] == x) return x; return fa[x] = get(fa[x]);}void merge(int x, int y){ fa[get(x)] = get(y);}bool same(int x, int y){ return get(x) == get(y);}int main(){ cin >> t; while (t--) { scanf("%d%d", &n, &m); for (int i = 0; i <=2* n; i++)//i表示D，i+n表示s fa[i] = i; getchar(); while (m--) { char op; int a, b; scanf("%c%d%d", &op, &a, &b); getchar(); if (op == 'D') { int a_d = a, a_s = a+n; int b_d = b, b_s = b + n; merge(a_d, b_s); merge(a_s, b_d); } else { if (same(a, b)) printf("In the same gang.\n"); else if (same(a + n, b)) printf("In different gangs.\n"); else printf("Not sure yet.\n"); } } } return 0;}
边带权：和奇偶游戏类似，不说了
#include#include using namespace std;const int N = 2e5 + 10;int fa[N],t,n,m,d[N];int get(int x){ if (fa[x] == x) return x; int root = get(fa[x]); d[x] ^= d[fa[x]]; return fa[x] = root;}void merge(int x, int y){ fa[get(x)] = get(y);}bool same(int x, int y){ return get(x) == get(y);}int main(){ cin >> t; while (t--) { scanf("%d%d", &n, &m); for (int i = 0; i <= n; i++)//i表示D，i+n表示s fa[i] = i,d[i]=0; getchar(); while (m--) { char op; int a, b; scanf("%c%d%d", &op, &a, &b); getchar(); if (op == 'D') { int p = get(a), q = get(b); fa[p] = q; d[p] = d[a] ^ d[b] ^ 1; } else { if (!same(a, b)) printf("Not sure yet.\n"); else if (d[a]^d[b]==1) printf("In different gangs.\n"); else printf("In the same gang.\n"); } } } return 0;}