PAT 甲級 05-樹7：文件傳輸網絡連通性（並查集 + 操作日誌）

題目建模

• N 台電腦（1~N 編號）
• 操作：
  • I c1 c2：建立雙向連接（合併集合）
  • C c1 c2：查詢是否連通（同集合？）
  • S：結束當前案例，輸出連通分量數

核心數據結構：並查集（Union-Find）

數組 S[]：負值表示根節點且絕對值為集合大小；非負值指向父節點。

Find（路徑壓縮）

int Find(int S[], int X) {
    X--;  // 轉 0-based
    for (; S[X] >= 0; X = S[X]);
    return X;
}

Union（按秩合併/按大小合併）

void Union(int S[], int X1, int X2) {
    int r1 = Find(S, X1), r2 = Find(S, X2);
    if (r1 != r2) {
        if (S[r1] <= S[r2]) {  // r1 更大（負值更小）
            S[r1] += S[r2];
            S[r2] = r1;
        } else {
            S[r2] += S[r1];
            S[r1] = r2;
        }
    }
}

查詢結果暫存策略

題目要求 S 後統一輸出所有 C 的結果，故用鏈表暫存：

typedef struct Flag { bool flag; struct Flag *next; } Flag;
Flag *head = malloc(sizeof(Flag)), *tail = head;
// C 操作時：
Flag *f = malloc(sizeof(Flag));
f->flag = (Find(S,c1) == Find(S,c2));
tail->next = f; tail = f;
// S 後遍歷輸出並釋放

最終連通分量統計

int k = 0;
for (int i = 0; i < N; i++) if (S[i] < 0) k++;
if (k > 1) printf("There are %d components.\n", k);
else printf("The network is connected.\n");

性能關鍵

• 數組實現並查集極快（7ms vs 結構體 150ms TLE）
• 路徑壓縮 + 按大小合併 → 擴展攤還 O(α(N))
• 輸入解析用 scanf("%c", &ch) 吃掉換行符

樣例驗證

輸入 1 對應輸出 1，輸入 2 對應輸出 2，邏輯完全吻合。