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