普通并查集 题目描述 在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足: 我朋友的朋友是我的朋友； 我敌人的敌人是我的朋友; 我的敌人的朋友是我的敌人； 我的朋友的敌人是我的敌人； 所有是朋友的人组成一个团伙。告诉你关于这n个人的m 条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？

这是一个典型的并查集问题。我们可以先将所有人看作是独立的集合，然后根据给出的信息，不断合并集合，最后统计集合的数量即可。

具体来说，我们可以用一个数组parent记录每个人所在的集合的代表元素，初始时每个人自成一个集合，即parent[i]=i。

然后，对于每条朋友关系，我们将两个人所在的集合合并。具体来说，我们可以找到两个人所在集合的代表元素（即它们的parent[i]），然后将其中一个集合的代表元素指向另一个集合的代表元素，这样它们就成为了一个集合。

对于每条敌人关系，我们需要将它们所在的集合标记为互相敌对。具体来说，我们可以将其中一个集合的代表元素的parent指向另一个集合的代表元素的相反数（为了区分敌人和朋友，我们将朋友的parent[i]设为正数，敌人的parent[i]设为负数），这样它们就成为了两个互相敌对的集合。

在合并集合时，我们还需要更新每个集合的代表元素的parent。具体来说，我们可以在find函数里使用路径压缩，将每个经过的点直接指向代表元素，从而加速后续的find操作。

最后，我们可以遍历每个人的parent，统计一共有多少个代表元素，即有多少个团伙。

以下是具体的实现代码：

相关问题

在某个城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足： 我朋友的朋友是我的朋友； 我敌人的敌人是我的朋友； 已知关于n个人的m条信息（即某2个人是朋友或者敌人），假设所有是朋友的人一定属于同一个团伙，请计算该城市最多有多少团伙？

这是一个典型的图论问题，可以使用并查集来解决。

首先，我们可以将每个人看作一个点，每条信息看作一条边，其中朋友关系对应联通的边，敌人关系对应不连通的边。由于已知所有朋友属于同一个团伙，所以我们只需要考虑每个连通块，每个连通块对应一个团伙。

接下来，我们可以使用并查集来快速判断两个人是否在同一个连通块中。具体来说，我们可以将每个人看作一个节点，最开始每个节点都是一个独立的集合，然后对于每一条朋友关系，将两个节点所在的集合合并为一个集合，表示这两个人在同一个连通块中。最后，统计有多少不同的集合，就是该城市最多有多少团伙。

具体实现时，可以使用一个数组parent[i]来表示节点i所在集合的根节点，初始时parent[i] = i，表示每个节点都是一个独立的集合。合并两个集合时，我们可以先找到它们的根节点，然后将其中一个根节点的父节点设置为另一个根节点，表示将这两个集合合并为一个集合。

以下是具体的代码实现：

pyth编程实现下列问题： 在某个城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足： 我朋友的朋友是我的朋友； 我敌人的敌人是我的朋友； 已知关于n个人的m条信息（即某2个人是朋友或者敌人），假设所有是朋友的人一定属于同一个团伙，请计算该城市最多有多少团伙？

可以使用并查集来解决此问题。首先初始化每个人自成一个集合，然后遍历所有信息，将每对朋友或敌人所在的集合合并。最后统计有多少个不同的集合即可，每个集合代表一个团伙。

以下是代码实现：

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表示敌人。函数返回值为城市中最多的团伙数量。