HDU 3172 Virtual Friends：帶權並查集（按秩合併）動態維護集合大小

問題描述

多測試用例。每案給 n 對好友關係 (name1, name2)，每次加入關係後輸出所在朋友圈總人數。名字長度 ≤ 20，總人數 ≤ 100,000。

算法：並查集 + 秩優化 + 字符串映射

• 用 unordered_map 或 Trie 將名字映射為整數 ID。
• 並查集數組 fa[] 存父節點，sz[] 存集合大小（僅根節點有效）。
• find(x)：路徑壓縮。
• unite(x,y)：按秩合併（sz[fx] < sz[fy] 交換），fa[fx]=fy, sz[fy]+=sz[fx]，返回 sz[fy]。
• 若已在同一集合，直接返回當前大小。

代碼亮點：Trie 加速字符串映射

代碼中實現了靜態 Trie（字典樹）進行名字→ID 映射，避免 unordered_map 的常數開銷，適合大數據量。每個節點存 ch[95]（可打印字符），val 為對應 ID。

完整參考代碼（精簡版，用 unordered_map）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int fa[MAXN], sz[MAXN];
int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); }
int unite(int x,int y){
    x=find(x); y=find(y);
    if(x==y) return sz[x];
    if(sz[x]>sz[y]) swap(x,y);
    fa[x]=y; sz[y]+=sz[x];
    return sz[y];
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin>>T;
    while(T--){
        int n; cin>>n;
        for(int i=0;i<2*n;i++) fa[i]=i, sz[i]=1;
        unordered_map mp;
        int id=0;
        while(n--){
            string a,b; cin>>a>>b;
            if(!mp.count(a)) mp[a]=id++;
            if(!mp.count(b)) mp[b]=id++;
            cout << unite(mp[a], mp[b]) << '\n';
        }
    }
    return 0;
}

總結

HDU 3172 是並查集維護集合大小的模板題，按秩合併 + 路徑壓縮保證近乎 O(1)，字符串映射用 unordered_map 或 Trie 均可，核心在於動態合併時返回新集合大小。