重み付きUnion Find (Weighted Union Find Tree)

ライブラリ

struct WeightedUnionFind{
    VI par;
    VI rank;
    VI diff_weight;

    WeightedUnionFind(ll sz){
        init(sz);
    }

    void init(ll sz){
        par.resize(sz);
        rank.resize(sz);
        diff_weight.resize(sz);
        FOR(i, 0, sz){
            par[i] = i;
            rank[i] = 0;
            diff_weight[i] = 0;
        }
    }

    int root(ll x) {
        if (par[x] == x) {
            return x;
        }
        else {
            ll r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }

    ll weight(ll x) {
        root(x);
        return diff_weight[x];
    }

    bool is_same(ll x, ll y) {
        return root(x) == root(y);
    }

    // weight(y) - weight(x) = w となるように merge する
    bool merge(ll x, ll y, ll w) {
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y), w = -w;
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }

    ll diff(int x, int y) {
        return weight(y) - weight(x);
    }
};

その他

  • rankは「必要?」と思いつつもそのまま入れた
    • 木を結合するときに深くなりすぎない効果
  • Weighted UFは「差分制約」言い換えると「相対情報」を扱える

他の問題