bouzuya.hatenablog.com

ぼうずやのにっき

強連結成分分解を調べた

今日のコミット。


競プロ典型 90 問の 021 経由で強連結成分分解 (SCC: Strongly Connected Component) を調べた。

強連結は有向グラフにおいて 2 つの頂点が互いに到達可能なこと。強連結成分分解は強連結になっている成分ごとに分解すること。それぞれの強連結成分を頂点として扱うと有向非巡回グラフ (DAG: Directed Acyclic Graph) になる。

蟻本 (第二版 4-3) にも書いてあった。上級じゃん……。

https://twitter.com/e869120/status/1385363292739104775