papamelon 349. 城市帮派 Find them, Catch them（挑战程序设计竞赛）

地址 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;
}

视频题解空间