matthew as a q.

目標10記事quant

強連結成分分解[アルゴリズム][メモ]

# 強連結成分とは

強連結成分とは、ある集合Sについて、任意のx, y in Sについて、x->yの有向道を持つもの。

 

# 強連結成分分解とは

有向グラフから、強連結成分を抽出するアルゴリズム

 

## アルゴリズム

### ある頂点vから深さ優先探索をし、行き止まりとなった順番をt(v)とする。

↑こう書くとスタートする頂点vによって、t(v)が変わるように見えるがほんと?

 

###  数字の大きな頂点から順に深さ優先探索する。行き止まりを見つけたら、そこまでに辿った頂点を1つの強連結成分とする。

 

### 辿ってない頂点がなくなるまで上記を繰り返す。