【ABC120】D - Decayed Bridges

atcoder.jp

解法

島をノード、橋を辺とするグラフを考える。

グラフの辺を削除するというのを、高速なアルゴリズムで実装するというのは難しい。
そのため、辺の削除をUnionFind-Treeなどを使って辺をつなげていくことで同じことを表現できないかを考えることにする。
(これは典型)

この問題では、辺を削除する順番が決まっているため、逆順に辺を追加していくことで答えを後ろから計算できそうな気がしてくる。
1~Mの全ての辺が削除された状態では、全ての島の組で不便な状態になっているため、不便さの合計は、になる。
ここで、M番目の辺を追加してみると、島の組のひとつが不便ではなくなるため、不便さの合計は、になる。
M-1, M-2, ..., とどんどん辺を追加していき、i番目の辺を追加したときの不便さの合計をans[i-1]とする。
i番目の辺を追加したとき、不便さは次のように計算できる。

• A[i]とB[i]が既に連結であったとき
  • 不便ではなくなる島の組は増えないため、不便さはans[i]になる。
• A[i]とB[i]が連結ではなかったとき
  • A[i]を含む連結成分の数をa、B[i]を含む連結成分の数をbとすると、不便さはans[i] - a * bになる。
  • A[i]を含む連結成分とB[i]を含む連結成分から1つずつ島を取り出すような、組み合わせ方がa * b

実装

struct UnionFind {
    vector<long long> par, siz;

    UnionFind(long long n) : par(n, -1) , siz(n, 1) { }

    // 根を求める
    long long root(long long x) {
        if (par[x] == -1) return x;
        else return par[x] = root(par[x]);
    }

    // x と y が同じグループに属するかどうか (根が一致するかどうか)
    bool issame(long long x, long long y) {
        return root(x) == root(y);
    }

    // x を含むグループと y を含むグループとを併合する
    bool unite(long long x, long long y) {
        x = root(x), y = root(y);
        if (x == y) return false; 
        if (siz[x] < siz[y]) swap(x, y);
        par[y] = x;
        siz[x] += siz[y];
        return true;
    }

    // x を含むグループのサイズ
    long long size(long long x) {
        return siz[root(x)];
    }
};

void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B){
    UnionFind Uf(N+1);
        
    // 答え
    vector<ll> ans(M, 0);
    // sum(n): 1~nまでの総和を返す
    ans[M-1] = sum(N-1);

    // 後ろから橋をつなげていく
    for (int i = M-1; i >= 1; i--) {
        // 既にA[i]とB[i]が行き来可能ではない場合
        if (!Uf.issame(A[i], B[i])) {
            ans[i - 1] = ans[i] - Uf.size(A[i]) * Uf.size(B[i]);
            Uf.unite(A[i], B[i]); // 橋を作る
        } else {
            ans[i - 1] = ans[i];
        }
    }
    REP (i, M) {
        cout << ans[i] << endl;
    }
}