2017-06-11 競技プログラミングにおける有向グラフに関する問題まとめ [強連結成分分解, 最小パス被覆, Dilworthの定理, トポロジカルソート] 競技プログラミング 有向グラフ トポロジカルソート 参考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個の辺張りでよくなる ちゃんとした解説記事が見当たらない。誰か書いておいてほしい 問題 トポロジカルソート EDPC Longest Path 解説 yukicoder No.517 壊れたアクセサリー 解説 CSA Digit Permutation 解説 CF460 Substring 解説 CF532 Andrew and Taxi 解説 AC Restore the Tree 解説 CF541 Gourmet choice 解説 強連結成分分解 AOJ 強連結成分分解 yukicoder No.19 ステージの選択 HR City Construction CSA72 Spring Cleaning AOJ 道路網改修 解説 DAGの最小パス被覆 AJ Merry Christmas 解説1 解説2 解説3 Dilworthの定理 IOI春合宿2016 マトリョーシカ人形 解説 AOJ Divisor 解説1 解説2 SRM557 Div1 Med Incubator 解説1 解説2 解説3 区間全部に有向辺を貼る yukicoder No.1014 competitive fighting 解説 CF Legacy 解説 ARC069 Flags 解説1 解説2
