ARC092 F - Two Faced Edges - koba-e964の日記

この手の全体の中から一つ取り除くタイプの問題は、「sigmaさんが『yosupoがこういうの得意です』と言っていたタイプの問題」という印象が強い。
F - Two Faced Edges

問題

N頂点M辺の有向グラフがある。各辺について、その辺だけの向きを反転した時、グラフの強連結成分(SCC)の個数が変わるかどうかを判定せよ。

2 <= N <= 1000
1 <= M <= 200000
グラフに自己ループや多重辺はない。互いに逆向きの辺はありえる。

解法

各辺a -> bについて、その辺を除いた時のa => bの到達可能性(A)と、b => aの到達可能性(B)が分かればよいことを示す。

A = trueのとき、a -> bを取り除いた後にSCCの個数は変化しない。B = falseなら、b -> aの辺を加えればaとbが同じSCCに属し、SCCの個数が1減る。B = trueなら、aとbはもともと同じSCCに属するので、b -> aの辺を加えてもSCCの個数は変化しない。
A = falseのとき、a -> bを取り除くとaからbへは到達不能になる。よってb -> aを加えるタイミングではSCCの個数は変化しない。B = trueの場合は、もともとaとbは同じSCCに属していたので、a -> bを取り除く時にSCCの個数が1個増える。B = falseの場合は、もともとaとbは別のSCCに属していたので、a -> bを取り除く時にSCCの個数は増えない。

以上より、各辺に対して上のAとBを求めれば良い。a -> bの有無はb => aの到達可能性には影響しないので、Bは簡単である。
Aについて調べたい。a => bへ辺a -> bを使わずに行けるのは、aから出る辺はa -> bより番号が小さいものしか使わずにbに行ける時か、aから出る辺はa -> bより番号が大きいものしか使わずにbに行ける時、およびその時に限る。(a以外から出る辺は全て使って良い。)よって、各頂点aおよびそこに接続する各辺e_i = (a -> b_i)からDFSをして、aから出るi番目以下の辺だけを使って到達可能な点、aから出るi番目以上の辺だけを使って到達可能な点を全て調べればよい。ナイーブにやるとO(M^2)かかるが、あらかじめ隣接リストを頂点ごとにソート・逆順ソートし、各DFSでインクリメンタルに更新することで、計算量をO(MN)に抑えることができる。
全体の計算量はO(N^2 + MN)である。

実装上の注意点

ボトルネックがO(MN)と重いので、極力重い定数倍を載せないようにする
隣接リストのソートをやっても良いが、普通にグラフを作るとそもそも不要
DFSをやる時に、連結性の更新処理のタイミングに注意を払う

提出: Submission #3929024 - AtCoder Regular Contest 092 (Rust)

type Idx = i32;
const INF: Idx = 1 << 20;

fn dfs<F>(g: &[Vec<(Idx, usize)>], lt: &F,
          conn: &mut [Idx], v: usize, cur: Idx)
where F: Fn(Idx, Idx) -> bool {
    if !lt(cur, conn[v]) { return; }
    conn[v] = cur;
    for &(_, w) in g[v].iter() {
        dfs(g, lt, conn, w, cur);
    }
}

// conn[i][j] = k: i -> j is reachable if you use edges from i with index <= k
// and edges that are not from i.
fn traverse<F>(g: &[Vec<(Idx, usize)>], lt: F, min: Idx) -> Vec<Vec<Idx>>
where F: Fn(Idx, Idx) -> bool {
    let n = g.len();
    let mut conn = vec![vec![-min; n]; n];
    for i in 0 .. n {
        conn[i][i] = min;
        for &(idx, w) in g[i].iter() {
            dfs(&g, &lt, &mut conn[i], w, idx);
        }
    }
    conn
}


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,
        ab: [(usize1, usize1)],
    }
    let mut g = vec![Vec::new(); n];
    for (i, &(a, b)) in ab.iter().enumerate() {
        g[a].push((i as Idx, b));
    }
    // g[i] is already in the increasing order
    let conn_orig = traverse(&g, |x, y| x < y, -INF);
    // decreasing order
    for adj in g.iter_mut() {
        adj.reverse();
    }
    let conn_rev = traverse(&g, |x, y| x > y, INF);
    for (i, (a, b)) in ab.into_iter().enumerate() {
        let i = i as Idx;
        let orig = conn_orig[a][b] != i || conn_rev[a][b] != i;
        let rev = conn_orig[b][a] < INF;
        puts!("{}\n", if orig ^ rev { "diff" } else { "same" });
    }
}

まとめ

本番解けずに(確か)rngさんの動画解説(通った辺のminやmaxみたいな何かを管理する)を聞いた時は「こんなの思いつけるわけないだろ」と思ったが、改めて考え直すと結構自然な考え方だと思った。
ただ最初自然に考えた結果「i番目未満の辺だけで行けるかi番目より大きい辺だけで行けるならOK」みたいになってしまい、サンプル1で間違いになった。(は?)

当然これは誤りで、サンプル1だと1 -> 3は1番目の辺1 -> 2と3番目の辺2 -> 3を両方使うことでのみ行ける