トポロジカルソートについて
こちらに参加したのですが,D問題で「トポロジカルソート」というテクニックが必要とのことで,調べました.
トポロジカルソート（英: topological sort）とは、グラフ理論において、有向非巡回グラフ（英: directed acyclic graph, DAG）の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。
とのこと.
非巡回グラフというのは、有向サイクル（矢印の向きにたどってノードを一周できるようなサイクル）が無いことを表します.
わかりやすく言えば, 任意の矢印に対して,
矢印が出ているノードの番号 < 矢印が入ってくるノードの番号
という関係が成り立つようにノードに番号を振り分けることができる, ということですかね。
証明は：cited from
有向非巡回グラフ（DAG）の意味とトポロジカルソート - 具体例で学ぶ数学
直感的でわかりやすい。
