题目

1385：团伙(group)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：

1、我朋友的朋友是我的朋友；

2、我敌人的敌人是我的朋友；

所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？

【输入】
第1行为n和m，1<n<1000,1<=m<=100 000；

以下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
【输出样例】
3

---

题目分析：第一条规定很容易实现，使用基本的并查集操作即可；第二条规定可以把每个人所有的敌人使用集合存储起来，操作和第一条就一样了。
具体方法是，为每个人建立一个结构体，包含两个成员，一个是自己的直接首领的编号(dboss)，一个是自己所有的敌人(enemies)。然后建立一个函数boss查找一个人所属团伙的最高首领。所有boss相同的人组成一个团伙。这样，当两个人是朋友时，就合并两个人所在的团伙，即将其中一个人的boss的dboss设为另一个人(的boss)；当两个人是敌人时，两个人分别与对方的敌人执行上述操作。最后，boss的数目就是所求数目。

---

C++代码

#include<iostream>
#include<unordered_set>
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

---

运行结果