2021-05-04 強連結成分分解を調べた

今日のコミット。

rust-sandbox 1 commit
- tasks: 0.1.0
  - tasks add <text>
  - serde, serde_json, dirs を使っている
rust-atcoder 4 commits

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

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

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