質問とシナリオ
グラフには n 個の頂点と m 本の有向辺があります。頂点には出次数が 0 のものがある可能性があり、辺は重複することがあり、グラフが連結であるとは限りません。強連結成分とは、どの2頂点間もお互いに到達可能な集合のことです。すべての成分を返し、それらを縮約することで有向非巡回グラフ（DAG）がどのように形成されるかを説明してください。
面接官がテストしていること
- 候補者がDFSのインデックス、
lowの値、スタックの所属状態、および成分IDを正しく維持できるか。 lowを更新する際に、木辺（tree edge）、後退辺（back edge）、およびすでに完了した成分への辺を区別できるか。- 非連結グラフ、自己ループ、多重辺、および再帰の深さのリスクを考慮しているか。
- O(n+m) の時間計算量と O(n) の補助空間を提示し、不変条件を検証できるか。
最初に確認すべき明確化のための質問
頂点IDが連続しているか、多重辺が許可されているか、成分の要素をソートする必要があるか、実行環境が再帰の深さを制限しているかを確認します。グラフのサイズ、差分更新の必要性、および同一成分判定クエリのみが必要かどうかを明確にします。非常に深いグラフについては、再帰と明示的なスタックのトレードオフを述べます。
30秒の回答フレームワーク
1回のDFSを実行し、各頂点に増加するインデックスと、後退辺によって到達可能な最小のインデックス（low と呼ばれる）を割り当てます。各頂点をプッシュしてマークし、隣接頂点を調べます。未訪問の隣接頂点に対しては再帰してその low を使用し、スタック上にまだ存在する隣接頂点に対してはそのインデックスを使用します。low がその頂点自身のインデックスと等しい場合、その頂点は成分の根（root）です。その頂点までポップします。各頂点と辺に対する処理は定数時間であるため、計算量は O(n+m) です。
ステップごとの詳細解説
- 状態を初期化する。 各頂点に対してインデックス、
low、スタック所属フラグ、および成分IDを保持します。非連結な入力をカバーするため、未訪問のすべての頂点からDFSを開始します。 - 未訪問の隣接頂点を処理する。 再帰呼び出しを行い、その後
low[u] = min(low[u], low[v])を適用します。これにより、DFS部分木からスタック上の以前の頂点へのパスが記録されます。 - スタック上の隣接頂点を処理する。 隣接頂点がまだスタック上にある場合は、隣接頂点のインデックスで
low[u]を更新します。すでに別の成分としてポップされた頂点は、このバックトラックに関与できません。 - 根を見つけてポップする。
low[u] == index[u]のとき、u は根です。u がポップされるまでポップを続け、所属フラグをクリアします。これらの頂点が1つの強連結成分を形成します。 - 境界ケースを処理する。 自己ループは単一頂点の成分を生成し、多重辺は同じ最小値更新を繰り返し、孤立頂点はプッシュされた時点で単一頂点の成分になります。
- 検証と縮約を行う。 すべての頂点が正確に1つの成分に属していること、および成分間の辺がDAGを形成していることを確認します。ランダムな小さなグラフで推移閉包やKosarajuのアルゴリズムと比較し、大きなグラフで計算量とスタックの深さをテストします。
高品質な回答例
私は4つの配列を保持します。増加する index、low バックリンク値、スタック所属フラグ、および成分IDです。DFS突入時にインデックスを割り当てて頂点をプッシュします。未訪問の隣接頂点については再帰してその low 値を伝播させ、スタック上にまだある隣接頂点についてはその隣接頂点のインデックスのみを伝播させます。完了した成分が更新に関与することはありません。
low[u] == index[u] のとき、u は根であるため、u までポップしてフラグをクリアします。連結性を前提としないよう、未訪問のすべての頂点からDFSを開始します。すべての頂点は1回プッシュされて1回ポップされ、すべての辺は1回調べられるため、時間計算量は O(n+m)、補助空間は O(n) になります。テストでは、自己ループ、多重辺、孤立頂点、長いチェーン、複数の閉路、非連結グラフに加えて、成分の分割と縮約DAGをカバーします。
よくある間違い
- 訪問済みのすべての隣接頂点の low 値から更新してしまい、誤って完了した成分をまたいでバックトラックしてしまう。
- 成分をポップした後にスタック所属フラグをクリアし忘れ、後続の辺が古い頂点を現在の祖先として扱ってしまう。
- 1つの頂点からのみDFSを開始し、非連結な入力で成分を見落とす。
lowが現在のインデックスと等しいことを、「辺がない」という意味ではなく「この頂点が成分の根である」という意味であると解釈しない。- 明示的なスタック、チャンク処理、またはランタイム設定について言及せずに、言語のスタック制限を超えてしまう。
フォローアップの質問と回答
ポップされた頂点が low を更新できないのはなぜですか？
その頂点はすでに完了した成分に属しており、現在のDFSパスにおけるバックトラックの祖先ではなくなっているためです。その low 値を使用すると成分の境界を越えてしまい、極大性が損なわれます。
各成分が1回だけポップされることをどのように証明しますか？
各頂点は1回プッシュされ、根だけがポップをトリガーできます。ポップ後、そのスタックフラグはクリアされ、DFSがそれを再びプッシュすることはないため、各頂点は正確に1つの成分に属します。
TarjanとKosarajuをどのように選び分けますか？
Tarjanは1回のDFSを使用し、転置グラフを必要としないため、トラバーサルとメモリ使用量を削減できます。Kosarajuは2回のDFSパスを使用し、各段階を明確に分離します。どちらも O(n+m) です。スタックの制限、可読性、既存のグラフ表現に基づいて選択します。