◉ 強連結成分分解

Kyopro Encyclopedia of Algorithms

これはステージング環境です。5 秒後に自動的に本番環境 (https://noshi91.github.io/algorithm-encyclopedia) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /algorithm-encyclopedia/strongly-connected-components#noredirect を利用してください。

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$ を深さ優先探索する方法¹と、lowlinkに着目して、構成する方法²がある。 接続する2頂点が $G$の同じ強連結成分に属する全ての辺を縮約することで得られるグラフが有向非巡回グラフであるという性質がある。

注釈

1. 強連結成分分解の意味とアルゴリズム | 高校数学の美しい物語^archive.org ↩

2. AtCoder Library の実装はこちらになっている。 ↩

---

View full history / Report issues / Edit this page

changelog

• 2021年03月04日「記事作成」 authors: udon1206, reviewers: noshi91

license

This work is licensed under a Creative Commons Attribution 4.0 International License.