给定n个人,他们之间有两个种关系,朋友与敌对。可以肯定的是:
与我的朋友是朋友的人是我的朋友
与我敌对的人有敌对关系的人是我的朋友
现在这n个人进行组团,两个人在一个团队内当且仅当他们是朋友。
求最多的团体数。
第一行一个整数n代表人数。
第二行一个整数m代表每个人之间的关系。
接下来m行每行一个字符opt与两个整数p,q
如果opt为 F 代表p与q为朋友。
如果opt为 E 代表p与q为敌人。
一行一个整数代表最多的团体数。
6 4 E 1 4 F 3 5 F 4 6 E 1 2
3
其实这道题本来是并查集的板子题,但是这里面有几个有趣的点:
1、反集思想:我们初始化2 * n 的数组,前一半表示朋友,后一半表示敌人(比如a + n表示a的敌人),如果两个是朋友,直接合并,如果两个是敌人,那么就合并 (a + n 和 b) 以及 (b + n 和 a)(b的敌人和a是朋友,a的敌人和b也是朋友),这样就可以表示出敌人的敌人是朋友了。
2、注意合并顺序:正如我前面括号里写的那样,我们要使用小的点作“父亲”节点,这样才能尽量保证在最后1->n 的遍历中找到最多的团伙
#include<bits/stdc++.h> using namespace std; int n,m; char c; int p[1000001] = { }; int tot = 0; int Find(int x) { return x == p[x] ? x : p[x] = Find(p[x]); } void merge(int x, int y) { int px = Find(x), py = Find(y); if(px == py) return; p[px] = py; } int main() { scanf("%d" ,&n); scanf("%d\n" ,&m); for(int i = 1; i <= n * 2; i++) { p[i] = i; } for(int i = 1; i <= m; i++) { scanf("\n%c" ,&c); int a,b; if(c == 'F') { scanf("%d %d" ,&a,&b); merge(a,b); } if(c == 'E') { scanf("%d %d" ,&a,&b); merge(b + n,a); merge(a + n,b); } } for(int i = 1; i <= n; i++) { if(p[i] == i) tot++; } printf("%d" ,tot); return 0; }