強連結成分分解 (SCC; Strongly Connected Component)
概要
有向グラフにおいて、お互いに行き来できる頂点をグループ化すること。
同じグループの頂点を1つにまとめることで、サイクルを含まないDAGになる。
コード例
アルゴリズム(典型90の解説より。理解できてない)
1. DFSをして、帰りがけ順に番号を記録
2. 辺の向きを逆転させ、番号の大きい順にDFS
問題例
参考URL
https://github.com/E869120/kyopro_educational_90/blob/main/editorial/021.jpg