ARC030 C問題

問題

C: 有向グラフ - AtCoder Regular Contest 030 | AtCoder

解法

強連結成分を取り除けば、有向非巡回グラフ(DAG)になる。得られたDAGをトポロジカルソートすることで、dp[頂点番号][文字番号]で動的計画法ができる。
強連結成分分解はアルゴリズムが確立されているが、ワーシャル・フロイドを行いu->vかつv->uとなる集合を計算することで求めた。
DFSを2回行う方法で強連結成分分解を行うと、分解と同時にトポロジカルソートもできるのでコード量も計算量も少なくなる。

計算量

コード