地址 https://www.papamelon.com/problem/349
一个城市里有两个帮派，另外有 N 个成员，成员从 1∼N 进行编号，每个成员来自于其中一个帮派。
给定 M 个信息，每个信息有两种格式：
D a b：a,b(1≤a,b≤N,a≠b) 两个人不是一个帮派的
A a b: 判断 a,b(1≤a,b≤N,a≠b) 两个人是否为同一个帮派
两人同属一个帮派则输出 In the same gang.
不同属一个帮派则输出 In different gangs.
根据现有的消息无法确定则输出 Not sure yet.
输入
第一行整数 T(1≤T≤20)，表示有多少组测试数据
每组测试数据格式如下：
第一行两个整数N,M(1≤N,M≤10^5)，表示成员的数量，消息的数量
接下来 M 行，每行一条消息，随机给出，格式如上所述
输出
对于每个 A 操作，需要一行结果，可能为 In the same gang.，In different gangs.，Not sure yet.
输入
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.
解答 并查集
两个帮派成员不是A就是B 不是敌对就是同伙
并查集N 表示帮派A N+1到2N表示帮派B
所以两个成员ab 要么a==b 要么a==b+N b==a+N
#include <iostream>
using namespace std;
const int N = 200020;
int f[N];
int n, m, t;
void init() {
for (int i = 0; i < N; i++) { f[i] = i; }
}
int find(int x) {
if (f[x] != x) { f[x] = find(f[x]); }
return f[x];
}
void merge(int a, int b) {
a = find(a); b = find(b);
if (a < b) {
f[b] = a;
}
else {
f[a] = b;
}
}
int main()
{
scanf("%d",&t);
while (t--) {
init();
scanf("%d%d",&n,&m);
for (int i = 0; i < m; i++) {
char op[2]; int a, b;
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'A') {
a = find(a); b = find(b);
int aN = find(a + n); int bN = find(b + n);
if (a == b) {
printf("In the same gang.\n");
}
else if (a == bN || b == aN) {
printf("In different gangs.\n");
}
else {
printf("Not sure yet.\n");
}
}
else {
merge(a,b+n);
merge(b, a + n);
}
}
}
return 0;
}