併查集

union_find.py

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True


dsu = DSU(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
    dsu.union(a, b)
print(dsu.find(2) == dsu.find(0))  # True
print(dsu.find(4) == dsu.find(5))  # False
print(len({dsu.find(x) for x in range(6)}))  # 3

python union_find.py