はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける有向グラフに関する問題まとめ [強連結成分分解, 最小パス被覆, 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個の辺張りでよくなる
    • ちゃんとした解説記事が見当たらない。誰か書いておいてほしい