並查集總結：路徑壓縮、按秩/按大小合並、應用例題

應用例：HDU 1856 最大朋友圈（求最大集合大小）。

非遞歸 find 實現

int find(int x) {
    int root = x;
    while (p[root] >= 0) root = p[root];
    while (x != root) { int tmp = p[x]; p[x] = root; x = tmp; }
    return root;
}

應用場景總結

• 動態連通性查詢（網絡、社交圖）。
• Kruskal 最小生成樹（檢測環）。
• 離線查詢（Tarjan LCA、並查集撤銷）。
• 集合大小/成員統計（按大小合並天然支持）。
• 二分圖檢測（帶權並查集/擴展域）。

模板代碼（通用版）

struct DSU {
    vector p, sz;
    DSU(int n=0) { init(n); }
    void init(int n) { p.resize(n); sz.assign(n,1); iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x]==x?x:p[x]=find(p[x]); }
    bool unite(int a, int b) {
        a=find(a); b=find(b); if(a==b) return false;
        if(sz[a]