题解 | #畅通工程#

class UnionFind:
    def __init__(self, n: int):
        self.parent = [i for i in range(n)]  # 初始化为：自己的父节点是自己
        self.rank = [0 for i in range(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):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] > self.rank[py]:  # 深度小的依附于深度大的
            self.parent[py] = self.find(px)
        elif self.rank[px] < self.rank[py]:
            self.parent[px] = self.find(py)
        else:  # 如果深度一样，则一方依附于另一方，最后记得深度加1
            self.parent[px] = self.find(py)
            self.rank[py] += 1


while True:
    try:
        ct = 0
        n, m = map(int, input().split(" "))  # n个城镇，m个道路
        if n == 0:
            break
        cz = UnionFind(n)
        for i in range(m):
            a, b = map(int, input().split(" "))
            cz.Union(a - 1, b - 1)
        for i in range(n):
            if cz.parent[i] == i:  # 如果是一个集合，则ct+1
                ct += 1
        print(ct - 1)
    except:
        break