C++ – 带权并查集

[ 络谷 ]

lli dsu[maxn];
lli dis[maxn];
lli num[maxn];

void init_dsu() {
    for (lli i = 0; i < maxn; ++i)
        dsu[i] = i;
    for (lli i = 0; i < maxn; ++i)
        dis[i] = 0;
    for (lli i = 0; i < maxn; ++i)
        num[i] = 1;
}

lli find_dsu(lli x) {
    if (dsu[x] == x) return x;
    lli f = find_dsu(dsu[x]);
    dis[x] += dis[dsu[x]];
    return dsu[x] = f;
}

void merge_dsu(lli a, lli b) {
    lli x = find_dsu(a);
    lli y = find_dsu(b);
    dsu[x] = y;
    dis[x] = num[y];
    num[y] += num[x];
    num[x] = 0;
}