hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング 有向グラフ トポロジカルソート 参考1 参考2 DAGにおいて、トポロジカルソート順にDPをするというのが、基本的な用法 強連結成分分解 SCC O(E+V) 有向グラフを任意の2頂点が強連結(互いに連結)である頂点集合を成分として分解する 強連結成分を縮約すると有向グラフがDAGになる(DPやトポロジカルソートができるようになる) 強連結成分分解を使って2-SAT問題が解ける これ 小ネタ ある無向グラフの辺に向きをつけて全体を強連結にできる ↔ 全ての次数が2以上 これ（この問題は構築が難しい） DAGの最小パス被覆 DAGのパス被覆の問題についての記事 DAGの最小パス被覆 2部マッチン… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2017%2F06%2F11%2F124732" title="競技プログラミングにおける有向グラフに関する問題まとめ [強連結成分分解, 最小パス被覆, Dilworthの定理, トポロジカルソート] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-06-11 12:47:32 rich https://blog.hamayanhamayan.com/entry/2017/06/11/124732 1.0 100%