要点：
基本的な定義を思い出してください：
- 2つのピーク（ $インライン$ u $インライン$ そして $インライン$ v $インライン$ ）からのパスが存在する場合、有向グラフは強連結と呼ばれます $インライン$ u $インライン$ で $インライン$ v $インライン$ そしてからの方法があります $インライン$ v $インライン$ で $インライン$ u $インライン$ 。
- 有向グラフは、頂点のいずれか2つが強く接続されている場合、 強接続と呼ばれます。
- 有向グラフの反転は、各エッジの方向を反対に変更する手順です
強く接続されたグラフの例：
以下に注意してください。
強い接続関係は、同値関係です。
$ inline $ 1）反射率：\ \ forall v \ v \ to v $ inline $
$ inline $ 2）Symmetry：\ \ forall v \ \ forall u \ v \ to u => u \ to v $ inline $
$ inline $ 3）推移性：\ forall v \ \ forall u \ \ forall t \ v \ to u \ \ edge u \ to t => v \ to t $ inline $
$ inline $ 2）Symmetry：\ \ forall v \ \ forall u \ v \ to u => u \ to v $ inline $
$ inline $ 3）推移性：\ forall v \ \ forall u \ \ forall t \ v \ to u \ \ edge u \ to t => v \ to t $ inline $
次に、 強連結成分は、強連結関係に関する有向グラフの頂点セットの等価クラスです。
したがって、私たちのタスクは、そのような等価クラスをすべて見つけることです。
小皿湯アルゴリズム
小皿湯の方法は、実装と理解が簡単です。 アイデアは、元のグラフとその反転が同じ高度に接続されたコンポーネントを持っているということです（本質的にサイクルであるため）。
有向グラフG =（V、E）を与えます。
G '=（V、E'）は、元のグラフGを反転したグラフです
次に、G 'で深さ検索を行います。 入場時間と退場時間（イン/アウト）をマークします。 頂点の頂点の追加の配列を取得しましょう。 終了時間の増加順にすべての頂点を追加します。 したがって、バーティクル配列は次のようになります。
ここで、元のグラフのアウトバックへのクロールを開始しますが、そのたびに、まだアクセスされていないクロールを選択し、バーティクル配列の最大インデックスを使用します。 1回のdfs反復中に訪れたすべての頂点は、接続されたコンポーネント（色でマーク）を形成します。
結論の代わりに：
グラフが隣接グラフで表されている場合、逆グラフでは必要ないので、同じグラフで作業できることに注意してください。 それ以外の場合は、O（V + E）で反転グラフを取得し、別のV + Eメモリで反転グラフを保存する必要があります。
ただし、アルゴリズムの主要部分は2つのDFS回避策で構成されています。 それぞれは、スパースグラフの場合はV + Eに、飽和グラフの場合はV ^ 2に比例して機能します。 頂点配列を保存するためにVメモリも必要です。