この手の全体の中から一つ取り除くタイプの問題は、「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, <, &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を両方使うことでのみ行ける