- name
- 強連結成分分解
- short description
- 有向グラフ $G = (V, E)$ の強連結成分 $C \subseteq V$ は、全ての $(u, v) \in C^2$ について $u$ から $v$ へ到達可能な極大集合である。$G$ の全ての強連結成分は $V$ の分割になり、これを強連結成分分解と呼ぶ。空間計算量、時間計算量ともに $O(\lvert V \rvert + \lvert E \rvert)$ で構成することができる。
- input
- 有向グラフ $G = (V, E)$
- output
- $G = (V, E)$ の強連結成分分解
- time complexity
- $O(\lvert V \rvert + \lvert E \rvert)$
- space complexity
- $O(\lvert V \rvert + \lvert E \rvert)$
概要
有向グラフ $G = (V, E)$ の強連結成分 $C \subseteq V$ は、全ての $(u, v) \in C^2$ について $u$ から $v$ へ到達可能な極大集合である。$G$ の全ての強連結成分は $V$ の分割になり、これを強連結成分分解と呼ぶ。空間計算量、時間計算量ともに $O(\lvert V \rvert + \lvert E \rvert)$ で構成することができる。実際に構成するアルゴリズムとして、$G$ と $G$ の転置グラフ $G ^ {\top} = (V, E ^ {\top}),\ E ^ {\top} = \lbrace (u,v) : (v, u) \in E \rbrace$ を深さ優先探索する方法1と、lowlinkに着目して、構成する方法2がある。 接続する2頂点が $G$の同じ強連結成分に属する全ての辺を縮約することで得られるグラフが有向非巡回グラフであるという性質がある。
注釈
-
AtCoder Library の実装はこちらになっている。 ↩
- changelog
- license
This work is licensed under a Creative Commons Attribution 4.0 International License.