https://blog.hamayanhamayan.com/entry/2017/06/11/124732

トポロジカルソート
- 参考1 参考2
- DAGにおいて、トポロジカルソート順にDPをするというのが、基本的な用法
強連結成分分解
- SCC
- O(E+V)
- 有向グラフを任意の2頂点が強連結(互いに連結)である頂点集合を成分として分解する
- 強連結成分を縮約すると有向グラフがDAGになる(DPやトポロジカルソートができるようになる)
- 強連結成分分解を使って2-SAT問題が解けるこれ
- 小ネタ
  - ある無向グラフの辺に向きをつけて全体を強連結にできる ↔ 全ての次数が2以上これ（この問題は構築が難しい）
DAGの最小パス被覆
- DAGのパス被覆の問題についての記事
- DAGの最小パス被覆
  - 2部マッチング問題に帰着させる
  - N頂点あれば、左右にN頂点用意して、i->jの辺があれば左のiと右のjの間に辺を貼る
  - 「N-最大マッチング」が最小パス被覆数となる
Dilworthの定理
- 有用そうなメモ
区間全部に有向辺を貼る
- こちらの解説中に雰囲気を書いた
- この図が参考になる
- セグメントツリーを用意して、有向辺を用意しておくことで、区間への辺張りがlogN個の辺張りでよくなる
- ちゃんとした解説記事が見当たらない。誰か書いておいてほしい