強連結 (strongly connected) とは
- 「有向」グラフにて、各頂点が行き来できる状態
強連結成分分解とは
- 有向グラフを、強連結なグラフに分解すること
縮約とは
- 頂点をマージすること
DAGとは
- Directed Acyclic Graph
- 有向グラフだけどサイクルしていない、つまり強連結ではないグラフ
強連結成分分解して縮約するとDAGになる
DAGになると？
- トポロジカルソートできるようになる
SCC
- Strongly connected component
- ライブラリ化された https://atcoder.jp/contests/practice2/tasks/practice2_g
- https://atcoder.github.io/ac-library/master/document_ja/
- 計算量 O(V+E)
SCCした結果を用いて、全体を強連結にするコスト
- 辺のweight=1とする https://stackoverflow.com/questions/14305236/minimal-addition-to-strongly-connected-graph
