并查集

#define N 100005
int st[N];
void uf_init() {
		memset(st, -1, sizeof(st));
}
int uf_find(int x) {
    return st[x]<0 ? x : st[x] = uf_find(st[x]);
}
void uf_union(int x, int y) {
    int fx = uf_find(x), fy = uf_find(y);
    if (fx != fy) {
        st[fx] += st[fy];
        st[fy] = fx;
    }
}

千万注意初始化。

using ll = long long;
struct Dsu {
    vector<ll> fa;
    Dsu(int sz) : fa(sz, -1){}
    
    int find(int u) {
        return fa[u] < 0 ? u : fa[u] = find(fa[u]); // 路径压缩
    }

    void unite(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            // 小集合fu 加入到 大集合fv，按秩归并
            if (fa[fu] < fa[fv]) swap(fu, fv);
            fa[fv] += fa[fu];
            fa[fu] = fv;
        }
    }
};

带权并查集

struct Wdsu {
    vector<ll> fa, wt;
    Wdsu(int sz) : fa(sz, -1), wt(sz, 0) {}
    int find(int u) {
        if (fa[u] < 0)
            return u;
        int v = find(fa[u]);
        wt[u] += wt[fa[u]];
        return fa[u] = v;
    }

    // 尝试u和v纳入同一集合，当路径权值冲突返回false
    /*
    u --val--> v
    u --wt[u]--> fu
    v --wt[v]--> fv

    fu == fv
    u --val--> v --wt[v]--> fv
    val + wt[v] = wt[u]

    fu !=fv
    fu --(val+wt[v]-wt[u])--> fv

    */
    int unite(int u, int v, int val) {
        int fu = find(u), fv = find(v);
        if (fu == fv) {
            return wt[u] == val + wt[v];
        }
        fa[fu] = fv;
        wt[fu] = val + wt[v] - wt[u];
        return true;
    }
};