\(N\) 頂点の有向グラフであって、各 \(i \, (1 \leq i \leq M)\) について頂点 \(A_i\) から頂点 \(B_i\) に辺が張られているようなものを考えると、トポロジカルソートした結果として辞書順最小のものが答えになります。

辞書順に関する問題では、前の要素から決めていくのが定石です。 前から順にトポロジカルソートした結果を求めていくアルゴリズムとして、以下のものが挙げられます。

• 空の数列 \(S\) を用意する。
• 入次数が \(0\) の頂点が存在する間、以下の処理を繰り返す。
  • 入次数が \(0\) の頂点を一つ選び \(u\) とする。
  • \(S\) の末尾に \(u\) を追加する。
  • \(u\) および \(u\) から出ている辺をグラフから削除する。
• アルゴリズムが終了した時点でグラフに頂点が残っているならば、トポロジカルソートすることは不可能である。グラフに頂点が残っていなければ、\(S\) がトポロジカルソートした結果になっている。

入次数 \(0\) の頂点として番号が最小のものを選ぶようにすると、\(S\) として辞書順最小のものが得られます。

実装例