Description
塔杜市警察局决定采取行动终结混乱，开展行动以根除市内的两个帮派：Dragon 帮和 Snake 帮。然而，警方首先需要确定一个罪犯属于哪个帮派。现在的问题是，给定两个罪犯，他们是否属于同一个帮派？你必须根据不完整的信息给出判断（因为歹徒总是秘密行动）。
假设塔杜市现有 \(N\) 个罪犯，编号从 \(1\) 到 \(N\)。当然，Dragon 帮和 Snake 帮都至少有一名成员。你将按顺序收到 \(M\) 条信息，信息分为以下两类：
-
D [a] [b]
其中 \([a]\) 和 \([b]\) 是两个罪犯的编号，这条信息表明他们属于不同的帮派。 -
A [a] [b]
其中 \([a]\) 和 \([b]\) 是两个罪犯的编号，这条信息需要你回答 \(a\) 和 \(b\) 是否属于同一个帮派。
Input
第一行包含一个整数 \(T\)（\(1 \le T \le 20\)），表示测试用例的数量。
随后是 \(T\) 组测试用例。每组测试用例的第一行包含两个整数 \(N\) 和 \(M\)，接下来 \(M\) 行，每行包含一条信息，格式如上所述。
Output
对于每个测试用例中的每条 A [a] [b] 信息，你的程序应根据在此之前获得的信息给出判断。答案可能是以下三者之一：
"In the same gang."（属于同一个帮派）"In different gangs."（属于不同帮派）"Not sure yet."（关系不确定）
Sample Input
1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4
Sample Output
Not sure yet.
In different gangs.
In the same gang.
数据范围
- \(1 \le N \le 10^5\)
- \(1 \le M \le 10^5\)
- \(1 \le a, b \le N\)
解题思路提示
这是一道经典的种类并查集（或带权并查集）问题。由于只有两个帮派，可以使用以下技巧：
- 将每个罪犯 \(x\) 拆分成两个点：\(x\) 表示其在 Dragon 帮，\(x + N\) 表示其在 Snake 帮。
- 对于
D a b操作：- 合并 \(a\) 与 \(b + N\)（a 在 Dragon 则 b 在 Snake）
- 合并 \(a + N\) 与 \(b\)（a 在 Snake 则 b 在 Dragon）
- 对于
A a b查询：- 如果 \(find(a) == find(b)\)，则属于同一帮派
- 否则如果 \(find(a) == find(b + N)\)，则属于不同帮派
- 否则关系不确定
#include <bits/stdc++.h>
using namespace std;
int T;int Fa[200002];
int GetFa(int k) {if (k==Fa[k]) return k;return Fa[k]=GetFa(Fa[k]);
}
void Merge(int x,int y) {int fx=GetFa(x);int fy=GetFa(y);if (fx!=fy) Fa[fy]=fx;
}
int main() {cin>>T;while (T--) {int n,m;cin>>n>>m;char ch;int a,b;for (int i=1;i<=n+n;i++) Fa[i]=i;for (int i=1;i<=m;i++) {scanf(" %c%d%d",&ch,&a,&b);if (ch=='D') {Merge(a,b+n);Merge(a+n,b);}if (ch=='A') {int f1,f2,f3,f4;f1=GetFa(a);f2=GetFa(b);f3=GetFa(a+n);f4=GetFa(b+n);if (f1==f2 || f3==f4) cout<<"In the same gang."<<endl;if (f1==f4 || f2==f3) cout<<"In different gangs."<<endl;if (f1!=f4 && f1!=f2) cout<<"Not sure yet."<<endl;}}}return 0;
}