ACM 并查集 食物链

并查集是一种用于解决集合合并与查询问题的数据结构。在食物链问题中，我们可以使用并查集来判断给定的K句话中有多少句是假话。

首先，我们需要创建一个并查集，其中每个动物都是一个节点。初始时，每个节点都是独立的集合。

然后，我们按照给定的K句话进行处理。对于每一句话，我们需要判断它是真话还是假话。

如果是第一种说法"1 X Y"，表示X和Y是同类。我们可以通过将X和Y所在的集合合并来实现。即将X所在的集合的根节点指向Y所在的集合的根节点，或者将Y所在的集合的根节点指向X所在的集合的根节点。

如果是第二种说法"2 X Y"，表示X吃Y。我们需要判断X和Y是否属于同一类。如果它们属于同一类，那么这句话就是假话。否则，这句话是真话。

最后，我们统计假话的总数即可。

以下是一个示例代码，演示了如何使用并查集解决食物链问题：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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 = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

def count_false_statements(N, K, statements):
    uf = UnionFind(N+1)
    false_count = 0
    for statement in statements:
        type, X, Y = statement
        if X > N or Y > N:
            false_count += 1
            continue
        if type == 1:
            if uf.find(X) == uf.find(Y+N) or uf.find(X+N) == uf.find(Y):
                false_count += 1
            else:
                uf.union(X, Y)
                uf.union(X+N, Y+N)
                uf.union(X+2*N, Y+2*N)
        elif type == 2:
            if uf.find(X) == uf.find(Y) or uf.find(X+N) == uf.find(Y):
                false_count += 1
            else:
                uf.union(X, Y+N)
                uf.union(X+N, Y+2*N)
                uf.union(X+2*N, Y)
    return false_count

N = 5
K = 7
statements = [(1, 1, 2), (2, 1, 3), (1, 2, 3), (2, 2, 4), (1, 4, 1), (1, 4, 3), (2, 4, 3)]
false_count = count_false_statements(N, K, statements)
print(false_count)  # 输出：3