1385：团伙(group)

题目

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
#include
using namespace std;
struct person
{short dboss;//该人的直接首领unordered_set<short> 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;
}

运行结果