Codeforces Round #490 (Div. 3)E. Reachability from the Capital
問題概要
頂点数 の有効グラフが与えられる. 頂点
からすべての頂点に到達可能にするには最小であと何本有向辺を追加すればよいか？
制約
解法
強連結成分分解をしたうえでトポロジカルソートをすれば, どの頂点に優先して辺を張ればいいかがわかります(よりトポロジカルソートしたときに早い頂点に辺を張りたいはずです).
ただし, から到達さえできればいいので, 次のようにすればいいです.
- 到達可能かどうかを表す bool 配列
を用意する. はじめ
で初期化する.
から到達可能な頂点
について, bfs などで
としておく.
- 頂点集合をトポロジカルソートし, 頂点番号の早い順にみていく. もし
なら辺を張ることにして答えに
を加算し, また
をすべて
に変更する.
- 答えを出力する.
このアルゴリズムではたかだか定数回しか各頂点を見ないので, 時間計算量 で答えを得ることができます.
実装
ACL の scc を用いると非常に実装が簡便です.
