強連結成分分解して縮約するとDAGになる

強連結とは

  • 「有向」グラフにて、各頂点が行き来できる状態

強連結成分分解とは

  • 有向グラフを、強連結なグラフに分解すること

縮約とは

  • 頂点をマージすること

DAGとは

  • Directed Acyclic Graph
  • 有向グラフだけどサイクルしていない、つまり強連結ではないグラフ

強連結成分分解して縮約するとDAGになる

f:id:peroon:20190529152231j:plain

DAGになると?

  • トポロジカルソートできるようになる

SCC

f:id:peroon:20200918050419p:plain