SDUT 並查集：統計與 0 號同學試卷相同的人數

問題描述

有 n 個學生（編號 0~n-1），已知 m 對關係 (a, b) 表示 a 和 b 試卷相同。求與 0 號學生試卷相同的其他學生人數（不含 0 號）。多組測試數據，EOF 結束。n ≤ 100000, m ≤ 10000。

解法：並查集

並查集完美支持「動態連通性」查詢。將每對關係 Union(a, b)，最後遍歷 1~n-1，統計 Find(i) == Find(0) 的個數。

核心操作

• MakeSet(n)：初始化 fa[i] = i。
• Find(x)：路徑壓縮 return fa[x] == x ? x : fa[x] = Find(fa[x])。
• Union(x, y)：fx = Find(x), fy = Find(y); if (fx != fy) fa[fy] = fx;（可加按秩優化）。

參考代碼（C++）

int fa[100010];

int Find(int x) {
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}

void Union(int x, int y) {
    x = Find(x); y = Find(y);
    if (x != y) fa[y] = x;
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 0; i < n; i++) fa[i] = i;
        for (int i = 0; i < m; i++) {
            int a, b; scanf("%d%d", &a, &b);
            Union(a, b);
        }
        int cnt = 0;
        for (int i = 1; i < n; i++)
            if (Find(i) == Find(0)) cnt++;
        printf("%d\n", cnt);
    }
    return 0;
}

複雜度

• 時間：O((n + m) α(n))，α 為反阿克曼函數，近似常數。
• 空間：O(n)。

總結

經典並查集入門題。路徑壓縮（+按秩合併）使操作幾乎為常數時間。注意數組大小開到 100010，輸入以 EOF 結束，輸出不含 0 號本身。