No.030 C

※ コードは WA が取れてない

まずは強連結成分分解する.

強連結成分内ではどのような順序のアルファベットの取り方もできる. よって, この成分内から $i$ 個のアルファベットを取ったときの辞書順最小は, 成分内のアルファベットを辞書順に並べた文字列の先頭 $i$ 文字である.

そこでグラフを強連結成分をひとまとめの頂点にしたグラフに書き換える. 新たな頂点には強連結成分に含まれるアルファベットを辞書順に並べたものを入れる.

これでグラフはDAGになるので, トポロジカルソートして(強連結成分分解でトポロジカルソートもできているはず), 後ろから順にその頂点で始まって $i$ 文字を回収したときの辞書順最小の文字列を DP で更新していく.