pyth编程实现下列问题: 在某个城市里住着n个人,任何两个认识的人不是朋友就是敌人,而且满足: 我朋友的朋友是我的朋友; 我敌人的敌人是我的朋友; 已知关于n个人的m条信息(即某2个人是朋友或者敌人),假设所有是朋友的人一定属于同一个团伙,请计算该城市最多有多少团伙?
时间: 2024-05-10 20:18:29 浏览: 257
可以使用并查集来解决此问题。首先初始化每个人自成一个集合,然后遍历所有信息,将每对朋友或敌人所在的集合合并。最后统计有多少个不同的集合即可,每个集合代表一个团伙。
以下是代码实现:
```python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.count = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
self.count -= 1
def max_groups(n, m, relations):
uf = UnionFind(n)
for relation in relations:
if relation[2] == 1: # 朋友关系
uf.union(relation[0], relation[1])
else: # 敌人关系
if uf.find(relation[0]) == uf.find(relation[1]):
uf.count -= 1
return uf.count
```
其中,输入参数n表示城市中的人数,m表示信息数量,relations是一个列表,每个元素表示一条信息,格式为(人A, 人B, 关系),关系为1表示朋友,为0表示敌人。函数返回值为城市中最多的团伙数量。
阅读全文