強連結成分
Tarjan のアルゴリズムで相互到達可能なノードをまとめます
「強連結成分」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
強連結成分とは
強連結成分とは、有向辺に沿って、どのノードからどのノードへも到達できるノードの極大なグループです。
重要な理由
各SCCを1つの超ノードにまとめると、任意の有向グラフをDAGに変換できます。これにより、相互依存関係を簡単に扱えるようになります。
Tarjanを1回の探索で実行する
Tarjanのアルゴリズムは、1回のDFSでSCCをすべて見つけます。計算量は O(V + E) で、通常の探索を1回行う場合と同じです。
発見番号
DFSが各ノードを初めて訪問した順に、発見時刻を割り当てます。この番号により、どのノードが先に発見されたかを比較できます。
disc = [-1] * n
timer = 0low-link値
各ノードのlow-linkは、後退辺を通る場合も含めて、そのノードから到達できる最小の発見番号です。これは成分の基準になります。
low = [-1] * nスタックに入れる
DFSでノードに入ったら disc と low を設定し、その成分を共有する可能性のあるノードのスタックに追加します。
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = True子からlowを更新する
未訪問の子へ再帰したら、その子の low 値を上へ反映します。low[u]は、自身の値と子の low の最小値になります。
dfs(v)
low[u] = min(low[u], low[v])後退辺を処理する
隣接ノードがすでにスタック上にある場合、それはこのSCC内の祖先です。その disc を使って low[u] を小さくします。
elif on_stack[v]:
low[u] = min(low[u], disc[v])成分の根を見つける
low[u] が disc[u] と等しいとき、ノード u はSCCの根です。スタック上でそのノードより上にあるすべてのノードが同じ成分に属します。
成分を取り出す
根に到達したら、u を取り出すまでスタックからノードを取り出します。このグループが、ちょうど1つの強連結成分です。
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: break別の方法: Kosaraju
2回の探索を使う方法がよければ、Kosarajuのアルゴリズムを使えます。DFSを行い、すべての辺を反転してから、終了順にもう一度DFSを行ってSCCを取り出します。
理解度チェック
TarjanのDFS中に、ノード u が low[u] == disc[u] を満たしました。これは何を示しますか？
まとめ: TarjanによるSCC
1回のDFSで disc と low を管理し、処理中のノードをスタックに積み、low と disc が等しいときに成分を取り出します。SCCを O(V+E) で求められます。🧩
よくある質問
「強連結成分」レッスンは無料ですか？
はい。「強連結成分」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「強連結成分」で何を学びますか？
Tarjan のアルゴリズムで相互到達可能なノードをまとめます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「強連結成分」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。