洛谷 P1892 [BalticOI 2003] 团伙 简单并查集 做法 题解

题目描述：

现在有 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; }