题目描述：

现在有 n 个人，他们之间有两种关系：朋友和敌人。我们知道：

• 一个人的朋友的朋友是朋友
• 一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

输入格式

第一行输入一个整数 n 代表人数。

第二行输入一个整数 m 表示接下来要列出 m 个关系。

接下来 m 行，每行一个字符 opt 和两个整数 p,q，分别代表关系（朋友或敌人），有关系的两个人之中的第一个人和第二个人。其中 opt 有两种可能：

• 如果 opt 为 F，则表明 p 和 q 是朋友。
• 如果 opt 为 E，则表明 p 和 q 是敌人。

输出格式

一行一个整数代表最多的团体数。

输入输出样例

输入 #1复制

6
4
E 1 4
F 3 5
F 4 6
E 1 2

输出 #1复制

3

说明/提示

对于 100% 的数据，2≤n≤1000，1≤m≤5000，1≤p,q≤n。

 

思路：

题目简单来说就是给出几对关系，有朋友关系也有敌对关系，要我们输出最终团体的数量。看到这种说两两关系的题我们可以想到用并查集来做，按题目的说法我们可以知道朋友的敌人的朋友就是敌人，敌人的敌人是朋友，都是朋友说明在一个团体。那么我们可以考虑扩展两倍n，做一个虚拟节点（n+1~2n）的操作，一半朋友，一半敌人，也就是n*2。然后是朋友就正常合并他们为一个团体（合并（x,y））,否则就是敌对，那么有"一对"关系，也就是x讨厌y，y讨厌x，那么我们可以进行两个合并，即合并（x+n，y），合并（y+n，x）。最后统计1到n的根节点数量，也就是团体数量，也就是答案。

举个例子：

假设 n=2，m=1，操作是 E 1 2（1 和 2 是敌人）。

1. 初始化：saki[1]=1, saki[2]=2, saki[3]=3, saki[4]=4
2. 执行 he(1+2, 2) → he(3, 2)，此时 saki[fin(3)] = fin(2) → saki[2] = 2（3 的根变成 2）
3. 执行 he(2+2, 1) → he(4, 1)，此时 saki[fin(4)] = fin(1) → saki[1] = 1（4 的根变成 1）

主播的代码（参考）:

#include <iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<string>
#include<math.h>
#include <iomanip>
#include<unordered_map>
#include <unordered_set>
#include<array>
#define gets(S) fgets(S,sizeof(S),stdin)
#define ll long long
const ll N = 1e6 + 5;
const ll Max = 0x3f3f3f3f;
using namespace std;

ll n, m, saki[N];

ll fin(ll x) {
	return saki[x] == x ? x : saki[x] = fin(saki[x]);
}

void he(ll x, ll y) {
	saki[fin(x)] = fin(y);
}

int main() {
	cin >> n >> m;

	for (int i = 1; i <= n * 2; i++) {
		saki[i] = i;
	}

	char c;
	ll x, y;
	for (int i = 1; i <= m; i++) {
		cin >> c;
		cin >> x >> y;
		if (c == 'F') {
			he(x, y);
		}
		else {
			he(x + n, y);
			he(y + n, x);
		}
	}

	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		if (fin(i) == i) {
			ans++;	
		}
	}
	cout << ans;

	return 0;
}