TopCoder SRM 684 (Div. 2) Hard. Autohamil
(2016/03/10) TLE する可能性のあるコードだったため修正しました。
問題概要
状態数が N の有限オートマトンが与えられる。すべての状態に訪れるような入力が存在するか判定せよ。
解法
強連結成分分解。
オートマトンと言ったが、実際のところある有向グラフがあって 0,..,N-1 の頂点をすべて訪れるような経路が存在するか判定する問題である。
同じ強連結成分の中では自由に移動できるため、ある強連結成分の中でひとつでも訪れることが可能な頂点があれば他すべて訪れることが可能である。
強連結成分というのは A→B の経路があれば B→A の経路もあるような A,B を同じグループとしてまとめたもの。
そこで強連結成分分解を行い強連結成分をひとつの頂点にまとめる。このようにしたグラフで 0 番の頂点からすべての頂点を辿れるかを DFS で判定すればいい。
強連結成分をまとめたグラフは DAG になるので、DFS は高速にできる。
(2016/03/10 追記)
- dp[v] := 頂点 v から辿れる最大の頂点数
として木 DP をすればいい。
DFS しなくても場合分けで分かりそうだが、ミスりそうなのでやめておく。
TopCoder SRM 684 (Div. 2) Hard. Autohamil
グラフを潰すところまでライブラリにしてあるから楽だったけど無い人には厳しい。
別解があるらしい？
(2016/03/10 追記)
n が小さいので Warshall-Floyd でも強連結成分分解ができます。こちらを使えばそんなに実装は重くなりません。
