group 1385：团伙 _团伙

题目
1385：团伙(group)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：
1、我朋友的朋友是我的朋友；
2、我敌人的敌人是我的朋友；
所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？
【输入】

文章插图
第1行为n和m，1
以下m行，每行为p x y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。
【输出】
一个整数，表示这n个人最多可能有几个团伙。
【输入样例】
6 4
1 1 4
0 3 5
0 4 6
1 1 2
【输出样例】
题目分析：第一条规定很容易实现，使用基本的并查集操作即可；第二条规定可以把每个人所有的敌人使用集合存储起来，操作和第一条就一样了。
具体方法是，为每个人建立一个结构体，包含两个成员，一个是自己的直接首领的编号(dboss)，一个是自己所有的敌人() 。然后建立一个函数boss查找一个人所属团伙的最高首领。所有boss相同的人组成一个团伙。这样，当两个人是朋友时，就合并两个人所在的团伙，即将其中一个人的boss的dboss设为另一个人(的boss)；当两个人是敌人时，两个人分别与对方的敌人执行上述操作。最后， boss的数目就是所求数目。
C++代码

#include#includeusing namespace std;struct person{short dboss;//该人的直接首领unordered_set enemies;//该人的敌人}ps[1005];short boss(short a)//查找一个人所属团伙的最高首领{if (ps[a].dboss != a)return boss(ps[a].dboss);return a;}void group_merge(short x, short y)//把x和y两个团伙合并{ps[boss(x)].dboss = boss(y);}int main(){int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i)//初始化ps[i].dboss = i;while (m--){bool p;short x, y;cin >> p >> x >> y;if (p)//我敌人的敌人是我的朋友{for (short i : ps[y].enemies){if (i != x)group_merge(x, i);}for (short i : ps[x].enemies){if (i != y)group_merge(y, i);}ps[x].enemies.insert(y);ps[y].enemies.insert(x);}else//我朋友的朋友是我的朋友group_merge(x, y);}short result = 0;//直接查不相同的最高首领有多少个bool b[1005]{};for (short i = 1; i <= n; i++){const short bs = boss(i);if (!b[bs]){++result;b[bs] = true;}}cout << result;return 0;}

【group1385：团伙】运行结果