Codeforces Round #520 (Div. 2) F. Upgrading Cities

この手の実装が重い問題を解くのにかなりの困難を感じる。
https://codeforces.com/contest/1062/problem/F

問題

サイクルのないn頂点m辺の有向グラフ(DAG)が与えられる。以下の条件を満たす頂点vを重要な頂点と呼ぶ:

任意の頂点wに対して、vからwへの道かwからvへの道が存在する。

また以下の条件を満たす頂点vを準重要な頂点と呼ぶ:

与えられたグラフからv以外のある頂点一つを取り除いて、vが重要な頂点になるようにできる。

与えられたグラフの重要な頂点と準重要な頂点の個数の合計を求めよ。

制約

2 <= n <= 300000
1 <= m <= 300000
与えられるグラフはDAG

解法

一般性を失わず、与えられたグラフがトポロジカルソートされている、つまり任意の辺(u, v)に対してu < vが成立していることを仮定してよい。
頂点iについて明らかなこととして、頂点iへ到達可能なのはiよりも小さい番号の頂点に限られ、頂点iから到達可能なのはiよりも大きい番号の頂点に限られる。これらは対称的なので、片方だけ考えればよい。つまり、各iについて、i以下の番号の頂点だけ見たときの、(頂点iへ到達不可能な頂点があるかどうか, 適当な1点を取り除いた時に頂点iへ到達不可能な頂点がないようにできるかどうか)がわかれば全てが解決する。

これを求めるにはどうしたら良いだろうか? まず、頂点iへ到達不可能な頂点があるかどうかについては、i以下の番号の頂点だけ見たとき出次数0の頂点がi以外にあるかどうかを判定すれば良い。これはインクリメンタルに出次数を管理していくことで、全てのiについて合計O(n+ m)時間で計算できる。
適当な1点を取り除いた時に頂点iへ到達不可能な頂点がないようにできるかどうかは少し難しい。まず、i以下の番号の頂点だけ見たときに、出次数0の頂点が2個以上であれば不可能であり、0個なら可能である。出次数0の頂点が1個の場合のみが問題だが、その頂点をxとした時、xへ向かう辺(w, x)があるようなすべての頂点wについて、xがなくなった時の出次数が0以外、つまり元々の出次数が2以上であればよい。これもデータ構造をうまく設計すればでき、各頂点vについて「vへの辺がある頂点の中で次数1のものが何個あるか」を管理すればよい。これも全てのiについて合計O(n + m)時間で行える。

同じことを辺を逆向きに張ったグラフに対しても行えば、合計O(n + m)時間で各頂点についての判定が行える。

登場する典型

トポロジカルソート
列を真ん中で区切って時系列データ2個に分ける
- iへ到達可能なのはiより小さい頂点だけ、iから到達可能なのはiより大きい頂点だけなので、綺麗に分割できる
- 分割した後の両方とも、小さい方から順番に作っていくインクリメンタルなアルゴリズムで計算できる

実装上の注意点

実装が重いので注意
- データ構造を管理するところで非常に間違えやすいので、デバッグプリントなどを使い正しいことを確かめる
逆辺を張ったグラフについても同じことをやるので、うまく共通化する
トポロジカル順序を考える必要があると大変なので、トポロジカル順序を使ってグラフそのものを書き換える
- 任意の辺(u, v)に対してu < vとなるようにしておくとかなり楽
HashSetよりBTreeSetの方が速い
- おそらく使い方の問題で、要素の追加、削除、1点集合の時に唯一の要素を取り出す、の3種類の操作だけが行われ、HashMapだと3番目の操作が遅い

提出: #51977370 (Rust, HashSet版)
#51982893 (Rust, BTreeSet版)

fn calc(g: &[Vec<usize>], revg: &[Vec<usize>], cnt: &mut [usize]) {
    let n = revg.len();
    let mut outdeg = vec![0; n];
    let mut zeroback = vec![0; n]; // zeroback[v] = #{w | (v -> u) in g, deg[v] = 1}
    let mut zero = 0;
    let mut zs = BTreeSet::new();
    for v in 0..n {
        for &w in &revg[v] {
            if outdeg[w] == 0 {
                zero -= 1;
                zs.remove(&w);
                zeroback[v] += 1;
            }
            if outdeg[w] == 1 {
                for &k in &g[w] {
                    if k < v {
                        zeroback[k] -= 1;
                    }
                }
            }
            outdeg[w] += 1;
        }
        cnt[v] += zero;
        if zero == 1 {
            let &x = zs.iter().next().unwrap();
            cnt[v] += zeroback[x];
        }
        zero += 1;
        zs.insert(v);
    }
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize,
        uv: [(usize1, usize1)],
    }
    let mut g = vec![vec![]; n];
    let mut revg = vec![vec![]; n];
    for &(u, v) in &uv {
        g[u].push(v);
        revg[v].push(u);
    }
    // find a topological order
    let mut ord = vec![];
    {
        let mut indeg = vec![0; n];
        let mut que = VecDeque::new();
        for i in 0..n {
            indeg[i] = revg[i].len();
            if revg[i].is_empty() {
                que.push_back(i);
            }
        }
        while let Some(v) = que.pop_front() {
            ord.push(v);
            for &w in &g[v] {
                indeg[w] -= 1;
                if indeg[w] == 0 {
                    que.push_front(w);
                }
            }
        }
    }
    assert_eq!(ord.len(), n);
    // Replace g and revg
    {
        let mut invord = vec![0; n];
        for i in 0..n {
            invord[ord[i]] = i;
        }
        for i in 0..n {
            g[i].clear();
            revg[i].clear();
        }
        for &(u, v) in &uv {
            let a = invord[u];
            let b = invord[v];
            g[a].push(b);
            revg[b].push(a);
        }
    }
    let mut cnt = vec![0; n];
    calc(&g, &revg, &mut cnt);
    cnt.reverse();
    for i in 0..n {
        for w in g[i].iter_mut() {
            *w = n - 1 - *w;
        }
        for w in revg[i].iter_mut() {
            *w = n - 1 - *w;
        }
    }
    g.reverse();
    revg.reverse();
    calc(&revg, &g, &mut cnt);
    cnt.reverse();
    let mut ans = 0;
    for i in 0..n {
        if cnt[i] <= 1 {
            ans += 1;
        }
    }
    puts!("{}\n", ans);
}

まとめ

ARC092 F - Two Faced Edges - koba-e964の日記にも通じるものがある気がする。今回は自力で解けたので嬉しかった。ただダラダラしてしまい実装に1.5時間近く掛かったのは反省。