2019-03-03

AtCoder ABC 120 D - Decayed Bridges (水色, 400 点)

とても教育的な問題ですね。

UnionFind 木の基本的な使い方 (連結成分のサイズ獲得含む)
クエリを先読みしておいて逆順に処理 (多くのクエリ先読み問題ではもっと変な順番で処理したりする)
差分のみ更新する考え方

といったあたりを学ぶことができる。

問題へのリンク

問題概要

$N$ 頂点 $M$ 辺の連結な無向単純グラフが与えられる。今、 $M$ 辺を順番に破壊していく。

$i$ 番目に破壊する辺は $a_i$ と $b_i$ を結ぶ辺

となっている。各 $i$ 回目の状態において以下のクエリに答えよ:

頂点のペアであって、互いに行き来できないものを数え上げよ

制約

$2 \le N \le 10^{5}$
$1 \le M \le 10^{5}$

考えたこと

一般にグラフのクエリ問題というのは、「辺を削除する」というのはめちゃくちゃ扱いづらいので、反対に「辺を追加する」と読み替えた方がいい。そういうことをする問題として、類題は (かなり難しいけど)

日経コン 2019 予選 E (800 点問題)
ARC 090 F - Donation (1000 点問題)

がある。

さて、というわけで、今回は反対に無から初めて逆順に辺を追加していくことにする。 $i$ 番目の状態というのは Union-Find で簡単に管理することができる。

欲しい情報は、 $i$ 番目において頂点を連結成分ごとに分けたときに、それぞれの連結成分が何個の頂点で構成されているかである。例えば、 $N = 8$ で連結成分が

(1, 6, 8)
(2, 3, 5)
(4, 7)

となっていたら、答えは

3 × 3 (1 グループ目の各頂点と 2 グループ目の各頂点)
3 × 2 (1 グループ目と 3 グループ目)
3 × 2 (2 グループ目と 3 グループ目)

を合計したものになる。

しかしこれでもまだ、計算量的には毎回のクエリに最悪 $O(N)$ の計算時間がかかってしまう (最悪全頂点を舐めないといけないため)。そこでさらなる工夫が求められる。

差分更新

反対に「i-1 番目の状態と i 番目の状態とがあまり大きくは変わらない」ということを生かして、その差分のみを素早く更新できたらいい。こういう考え方もまた、400 点問題あたりから頻出になって来る。

今回、i 番目の辺 (a, b) を追加する状況について考えてみる。

もし a と b とが既に同じ連結成分に入っていたら、答えは変わらない
a と b が異なる連結成分に入っていたとする。このとき a 側のサイズを sa、b 側のサイズを sb とする。そうすると、a と b とがつながることによって、新たに sa × sb 個のペアが互いに行き来できることになる (これを i-1 番目の答えから引く)

という風になる。あとはこれを素直に実装する。計算量は $O(N + M\alpha(N))$ となる。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    long long N, M; cin >> N >> M;
    vector<int> A(M), B(M);
    for (int i = 0; i < M; ++i) {
        cin >> A[i] >> B[i], --A[i], --B[i];
    }
        
    UnionFind uf(N);
    long long cur = N * (N-1) / 2;
    vector<long long> res;
    for (int i = 0; i < M; ++i) {
        res.push_back(cur);
            
        int a = A[M-1-i], b = B[M-1-i];
        if (uf.issame(a, b)) continue;
        
        long long sa = uf.size(a), sb = uf.size(b);
        cur -= sa * sb;
        uf.merge(a, b);
    }
        
    reverse(res.begin(), res.end());
    for (int i = 0; i < res.size(); ++i) cout << res[i] <<endl;
}

補足: 連結成分のサイズも取得する Union-Find

Union-Find 木の union 部分の実装ポリシーは二種類あって

union by rank (蟻本はこっち)
union by size

とがある。union by size はアイディアは簡単で、

x を根とする連結成分
y を根とする連結成分

とを比較して、「サイズが小さい方を、大きい方につなぐ」というもの。

これをすることで、処理を高速化できる。その原理はいわゆる「データ構造をマージするテク」と本質的に同じもの。

また union by size による方法の副産物的なメリットとして、

x を含む連結成分のサイズ

を簡単に取り出すことができる。

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 120 D - Decayed Bridges (水色, 400 点)

問題概要

制約

考えたこと

差分更新

コード

補足: 連結成分のサイズも取得する Union-Find