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

hamayanhamayan's blog

競技プログラミングにおける有向グラフに関する問題まとめ [強連結成分分解, 最小パス被覆, Dilworthの定理, トポロジカルソート]

強連結成分分解

  • SCC
  • O(E+V)
  • 有向グラフを任意の2頂点が強連結(互いに連結)である頂点集合を成分として分解する
  • 強連結成分を縮約すると有向グラフがDAGになる(DPやトポロジカルソートができるようになる)
  • 強連結成分分解を使って2-SAT問題が解ける これ

DAGの最小パス被覆