HDU 並查集社交網絡：動態維護集合大小

題目大意

輸入多組測試用例，每組給出 m 條好友關係（字符串名字），每加入一條關係後，輸出該社交網絡當前的總人數（即所在連通分量大小）。

核心技巧：字符串映射 + 並查集維護 size

• 用 `unordered_map` 將名字映射為整數 ID
• 並查集數組 `fa[]`、`sz[]`，`sz[root]` 存儲該集合大小
• 合併時 `sz[new_root] += sz[old_root]`

代碼實現

const int MAXN = 200005; // 2*m 上限
int fa[MAXN], sz[MAXN];
unordered_map id_map;
int idx = 0;

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

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a != b) {
        fa[a] = b;
        sz[b] += sz[a];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int m; cin >> m;
        id_map.clear(); idx = 0;
        for (int i = 0; i < m; ++i) {
            string a, b; cin >> a >> b;
            if (!id_map.count(a)) { id_map[a] = ++idx; fa[idx] = idx; sz[idx] = 1; }
            if (!id_map.count(b)) { id_map[b] = ++idx; fa[idx] = idx; sz[idx] = 1; }
            unite(id_map[a], id_map[b]);
            cout << sz[find(id_map[a])] << '\n';
        }
    }
}

關鍵點

• 每次輸出 `sz[find(x)]` 而非 `sz[x]`，確保取到根節點的正確大小
• 路徑壓縮不影響 `sz` 正確性，因 `sz` 只在根節點維護
• 初始化 `sz[i]=1` 表示單人集合大小為 1
• 用 `ios::sync_with_stdio(false)` 加速 IO

複雜度

• 時間：O(m α(m))，近似線性
• 空間：O(m)