モーニングルーティン制定【トポロジカルソートあり】

はじめに

みんなモーニングルーティンってありますか？
僕はまだないので、今から制定していきます。

手順１：ルーティンの列挙

まずは朝起きてから毎日やりたいことを列挙してみます。
例えば

顔を洗う
歯を磨く
服を着替える
寝癖をなおす
コーヒーを淹れる
コーヒーを飲む

など

手順２：依存関係の検討

手順１で挙げたルーティンたちの間には、依存関係があったりなかったりします。
例えば

コーヒーを飲むのは、コーヒーを淹れた後の方がよい。
歯を磨くのは、コーヒーを飲んだ後の方がよい。
- コーヒーがミント味になってしまうので
服を着替えるのは、顔を洗ったあとの方がよい。
- せっかく着替えた服がびしょ濡れになってしまうので
寝癖をなおすのは、服を着替えた後の方がよい。
- 服を脱ぐときに結局髪が乱れるので

など
これをすべてのペアについて検討しておきます。

手順３：実行順の決定

あとは、手順２の要求がすべて満たされるようにルーティンの実行順を決めればモーニングルーティン完成です。
これは、手順１の各ルーティンをノード、手順２の依存関係を有向辺とみたグラフをトポロジカルソートすることと同じなので、以下のアルゴリズムを適用すればよいです（Wikipediaより引用）。

L ← トポロジカルソートした結果を蓄積する空リスト
S ← 入力辺を持たないすべてのノードの集合

while S が空ではない do
S からノード n を削除する
L に n を追加する
for each n の出力辺 e とその先のノード m do
辺 e をグラフから削除する
if m がその他の入力辺を持っていなければ then
m を S に追加する

if グラフに辺が残っている then
閉路があり DAG でないので中断