プロンプトと適用可能なコンテキスト
0 から n - 1 までのラベルが付いた n 個のノードと、各ペア [u, v] が無向エッジを表す配列 connections が与えられます。グラフは連結かつ単純グラフであり、自己ループや多重辺はありません。グラフを非連結にするすべてのエッジである重要接続（critical connection）をすべて返してください。 答えの出力順序は問われず、各エッジの端点の順序もどちらでも構いません。
2 <= n <= 100000 および n - 1 <= connections.length <= 100000 であると仮定します。例：
n = 4
connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
output = [[1, 3]]最初の 3 本のエッジはサイクルを形成しているため、そのうちのいずれか 1 本を削除しても代替ルートが残ります。ノード 3 はエッジ [1, 3] のみを持っており、これを削除するとノード 3 は分離されます。グラフ理論の用語では、重要接続は橋（bridge）と呼ばれます。
これはグラフの不変条件（invariant）に関するコーディング問題です。エッジが追加されるにつれて連結成分を維持する既存の Union-Find の記事とは異なり、有向非巡回グラフ（DAG）を順序付けるトポロジカルソートとも異なり、重み付き経路長を最適化するダイクストラ法とも異なります。ここでは、各無向エッジを削除した後に連結性がどのように変化するかによって出力が決まります。
面接官が評価するポイント
第 1 のシグナルは、提示された規模において、候補者が単純な探索の繰り返しアプローチを退けるかどうかです。1 本のエッジを削除して BFS や DFS を実行すれば 1 回のクエリには正しく答えられますが、それを m 本のエッジすべてに対して繰り返すと O(m(n + m)) の時間がかかります。100,000 本のエッジがある場合、エッジごとに線形走査を行う方法は現実的ではありません。
第 2 のシグナルは、正確な low-link の不変条件の把握です。DFS の発見時刻 tin[u] は、u が最初に訪問された時刻を記録します。low[u] は、u の DFS 部分木から木の親・子エッジ（tree edge）を下り、最大 1 本の非木エッジ（後退辺など）を使用して到達できる最も早い発見時刻です。DFS 木のエッジ u -> v について、そのエッジが橋であるための必要十分条件は low[v] > tin[u] です。
第 3 のシグナルは、実装の厳密さです。すでに訪問済みの隣接ノードについては、low[neighbor] ではなく tin[neighbor] で更新します。ノードに入ってきた際に使用した正確なエッジをスキップするのであり、「もう一方の端点が親と一致するすべてのエッジ」をスキップするのではありません。エッジ ID を使用してこの区別を明示することで、フォローアップで多重辺が許可された場合でもコードの正当性が保たれます。
第 4 のシグナルは、本番環境向けの言語仕様への配慮です。再帰的な DFS は簡潔ですが、100,000 ノードの一本道（チェイン）では JavaScript ランタイムのコールスタック制限を超える可能性があります。反復型 DFS では、子の処理が終了した後にのみ low の値を親へ伝播できるように、進入フェーズと子からの復帰フェーズの両方をシミュレートする必要があります。
回答前に確認すべき質問
- グラフは有向グラフですか？ いいえ。有向グラフにおける橋は定義もアルゴリズムも異なります。
- グラフは連結であることが保証されていますか？ 基本の設問では保証されています。未訪問ノードすべてに対してループを回す処理は漸近的なコストがかからず、非連結グラフのフォローアップにもそのまま対応できます。
- 多重辺は許可されますか？ 基本の設問では許可されません。ただし、本実装では各エッジに ID を付与しているため、2 本の平行なエッジが存在しても双方が誤って橋として報告されることはなく、正しく代替ルートとして処理されます。
- 結果のエッジの端点の順序は任意ですか？ はい。もしジャッジ環境が正規化された出力を要求する場合は、各エッジを
[min, max]に正規化し、橋をすべて検出した後にのみソートしてください。 - グラフは静的ですか？ はい。エッジの挿入や削除が行われる中で橋を維持するのは動的連結性（dynamic connectivity）の問題であり、更新ごとにこの線形アルゴリズムを再実行するのはコストが高すぎる場合があります。
- 再帰を使用してもよいですか？ 実行環境が十分なスタック深さを保証している場合に限られます。JavaScript や TypeScript で
nが最大 100,000 の場合、明示的なスタックを用いるのがより安全な設計です。
30秒の回答フレームワーク
「DFS を 1 回実行し、各ノードに発見時刻 tin を割り当てます。各ノードについて、low は、ノードに入った木のエッジを逆戻りすることなく、その DFS 部分木から到達できる最も早い発見時刻を記録します。子ノード v の処理が完了した際、もし low[v] > tin[u] であれば、v 以下の部分木から u やその祖先へのルートが存在しないため、[u, v] は橋となります。そうでなければ後退辺が代替ルートを提供しています。多重辺のフォローアップにも対応し、コールスタックのオーバーフローを防ぐため、エッジ ID と明示的な DFS スタックを使用します。すべての隣接エッジは 1 回ずつ処理されるため、時間計算量は O(n + m)、空間計算量は O(n + m) です。」
ステップバイステップの詳細解説
まずは、正しくはあるものの低速なベースラインから考えます。各エッジについて一時的にそれを除外して一方の端点から探索を行います。もう一方の端点に到達できなくなった場合、そのエッジは橋です。1 回の走査に O(n + m) かかるため、すべてのエッジに対して行うと O(m(n + m)) かかります。この手法は極小のグラフや単発の検証には監査しやすいため適している場合もありますが、求められる規模には対応できません。
DFS を用いると、1 パスですべての代替ルートを明らかにできます。ノード u に初めて入ったとき、tin[u] = low[u] = timer を代入し、timer をインクリメントします。新しく訪問した隣接ノードは DFS 木の子になります。別エッジ経由で到達した訪問済みの隣接ノードは非木接続となるため、low[u] を tin[neighbor] に引き下げることができます。子ノード v の処理が完了すると、その部分木全体が確定し、low[u] = min(low[u], low[v]) によってその到達可能性が親へと伝播します。
不等号が厳密（strict）であることが重要です。low[v] < tin[u] の場合、子の部分木は u の祖先に到達できます。low[v] == tin[u] の場合、別のルートを通って u 自身に到達できます。いずれの場合も、木のエッジ [u, v] はサイクル上に存在することを意味します。low[v] > tin[u] である場合のみ、子の部分木からすでに発見された側へのすべてのルートが [u, v] を経由せざるを得ないことが証明されます。
反復型実装では、次に調べるべき隣接リストのインデックスである nextIndex[u] を保持します。ノードは子が実行されている間スタック上に残ります。そのノードのすべての隣接エッジが消費されるとスタックからポップされます。このポップされるイベントが再帰呼び出しからの復帰をシミュレートしており、親の値を更新する正しいタイミングとなります。
type AdjacentEdge = readonly [to: number, edgeId: number]
function findCriticalConnections(
n: number,
connections: ReadonlyArray<readonly [number, number]>,
): number[][] {
const graph: AdjacentEdge[][] = Array.from({ length: n }, () => [])
connections.forEach(([from, to], edgeId) => {
graph[from].push([to, edgeId])
graph[to].push([from, edgeId])
})
const tin = new Array<number>(n).fill(-1)
const low = new Array<number>(n).fill(-1)
const parent = new Array<number>(n).fill(-1)
const parentEdge = new Array<number>(n).fill(-1)
const nextIndex = new Array<number>(n).fill(0)
const bridges: number[][] = []
let timer = 0
for (let root = 0; root < n; root += 1) {
if (tin[root] !== -1) continue
tin[root] = timer
low[root] = timer
timer += 1
const stack = [root]
while (stack.length > 0) {
const node = stack[stack.length - 1]
if (nextIndex[node] < graph[node].length) {
const [neighbor, edgeId] = graph[node][nextIndex[node]]
nextIndex[node] += 1
if (edgeId === parentEdge[node]) continue
if (tin[neighbor] === -1) {
parent[neighbor] = node
parentEdge[neighbor] = edgeId
tin[neighbor] = timer
low[neighbor] = timer
timer += 1
stack.push(neighbor)
} else {
low[node] = Math.min(low[node], tin[neighbor])
}
} else {
stack.pop()
const parentNode = parent[node]
if (parentNode !== -1) {
if (low[node] > tin[parentNode]) {
bridges.push([parentNode, node])
}
low[parentNode] = Math.min(low[parentNode], low[node])
}
}
}
}
return bridges
}外側のループは連結な基本入力に対しては冗長ですが、連結性の保証が外された場合でも各成分で正しく DFS を開始できます。エッジ ID の使用は親ノードによるスキップよりも堅牢です。u と v の間に 2 本の多重辺がある場合、子は木エッジのみをスキップし、2 本目のエッジは代替ルートとして認識され、その low 値を引き下げます。
正当性について、v の処理完了後における DFS 木のエッジ u -> v を考えます。low[v] の定義より、値が最大でも tin[u] であることは、v の部分木から u またはその祖先への非木ルートが存在することを証明します。木パスと組み合わせると、そのルートは [u, v] を含むサイクルを形成するため、エッジを削除しても部分木が分離されることはありません。もし low[v] > tin[u] であれば、そのようなルートは存在しません。その部分木から既知のノード群へのあらゆるパスは [u, v] を通過しなければならず、これを削除すると連結成分の数が増加します。したがって、この条件は必要十分条件です。
各無向エッジは隣接リストに 2 回現れ、各エントリは 1 回ずつ調べられます。各ノードは 1 回ずつプッシュおよびポップされます。時間計算量は O(n + m) です。グラフ、配列、スタック、出力は O(n + m) の空間を使用します。グラフと返却する解を除いた補助空間は O(n) です。
結果の順序は指定されていないため、コーナーケースのテストでは正規化されたエッジの集合を比較すべきです。1 本のエッジのみの場合は橋である必要があります。サイクルには橋があってはならず、木のすべてのエッジは橋である必要があり、1 本のエッジで結ばれた 2 つのサイクルではその接続エッジのみが報告される必要があります。また、再帰スタックのリスクを検証するために 100,000 ノードの一本道もテストしてください。さらなる確証を得るために、小さなランダムグラフを生成し、線形アルゴリズムの結果を「1 本ずつエッジを削除するベースライン」と比較してください。
質の高い模範解答
「直接的な解法としては、各エッジを削除して走査を再実行する方法がありますが、これには O(m(n + m)) のコストがかかります。発見時刻と各 DFS 部分木から到達可能な最も早い発見時刻を記録することで、1 回の DFS を再利用できます。
ノード u に入るとき、tin[u] と low[u] を現在のタイマー値に初期化します。木の子ノードは完全に処理されてから、その low の値が u に伝播されます。別のエッジ経由で到達した訪問済みの隣接ノードに対しては、その隣接ノードの tin で更新します。そのエッジ自体が不変条件で表される『1 本の非木エッジによる脱出路』だからです。
子ノード v の処理完了後、[u, v] が橋であるための条件は厳密に low[v] > tin[u] です。等号では不十分です。等号は部分木から u へ戻る別のルートが存在することを意味し、そのエッジがサイクルに属していることを示します。より大きい値であることは、部分木内のどのノードもその木エッジを使わずに u や祖先に到達できないことを意味し、エッジの削除によって部分木が分離されます。
100,000 ノードという制約のため、DFS を反復型で実装します。スタックはすべての隣接エントリが処理されるまでノードを保持し、これにより子の low 値を伝播するための復帰イベントが得られます。また、親エッジの ID を保持し、そのエッジのみを正確にスキップします。これにより多重辺のフォローアップも正しく処理できます。すべての隣接エントリは 1 回だけ検査されるため、時間計算量は O(n + m)、合計空間計算量は O(n + m) です。サイクル、木、1 本のエッジで繋がれた 2 つのサイクル、長い一本道、非連結成分、多重辺をテストし、さらに小さなランダムグラフを用いてベースラインとの差分テストを行います。」
よくある間違い
- エッジごとに DFS を再実行する → 正当性は問題ないものの最悪ケースが二次時間以上になる → 1 回の DFS を使用し、代替ルートの情報を
lowに保持する。 low[child] >= tin[parent]をチェックしてしまう → 等号はすでに親への別パスが存在することを証明している → 厳密な条件low[child] > tin[parent]を使用する。- 訪問済みの隣接ノードを
low[neighbor]で更新してしまう → 別の DFS 部分木からの到達可能性が非木エッジを越えて漏れ出し、本物の橋を見逃す可能性がある → 訪問済みの隣接ノードにはtin[neighbor]を使用し、low[child]は木の子ノードの処理完了後にのみ使用する。 - 親ノードへのすべてのエッジをスキップしてしまう → 多重辺がすべて無視され、一方が誤って橋として報告される可能性がある → エッジ ID を割り当て、ノードに入るために使用したエッジのみをスキップする。
- 子の処理が完了する前に橋の判定を行ってしまう → 子の代替ルートがまだ判明していない → シミュレートされた復帰フェーズ中に条件を評価する。
- ノード 0 からしか開始しない → 非連結のフォローアップで他の成分を取りこぼす → 未訪問のすべてのノードから開始する。
- スタック制限を確認せずに再帰を使用する → 線形計算量であっても長い一本道で失敗する可能性がある → 明示的なスタックを使用するか、ランタイムが必要な深さをサポートしていることを確認する。
フォローアップの質問と回答
フォローアップ 1: グラフが非連結の場合は何が変わりますか？
橋の定義を「そのエッジを削除すると連結成分の総数が増加するエッジ」と定義します。各連結成分の内部で同じ low-link の条件が適用されます。発見時刻がまだ -1 のままのすべてのノードから DFS を開始します（提示した実装はすでに対応しています）。削除後にグラフ全体が非連結になることまでは要求しません。
フォローアップ 2: 多重辺や自己ループが許可される場合はどうなりますか？
すべてのエッジに一意の ID を保持し、parentEdge[node] のみをスキップします。親への 2 本目のエッジは非木ルートとして機能し、いずれの多重辺も橋として判定されないようになります。自己ループはノードを自身の発見時刻で更新するため、橋になることは絶対にありません。基本の設問では両方とも除外されていますが、実装のエッジ識別機能により適切に拡張されます。
フォローアップ 3: 代わりに関節点（Articulation Points）を返すにはどうすればよいですか？
low-link のデータは再利用できますが、条件がエッジから頂点に移ります。根以外のノード u は、low[v] >= tin[u] を満たす DFS の子 v を持つ場合に関節点となります。DFS 木の根は、DFS 木の子を 2 つ以上持つ場合にのみ関節点となります。頂点の条件には等号が含まれるのに対し、橋の検出には厳密な不等号 > が使用される点に注意してください。
フォローアップ 4: エッジが継続的に追加される場合は何が変わりますか？
このアルゴリズムは静的なスナップショットに対して線形時間で答えるものです。挿入のたびに再計算を行うと、更新ごとに O(n + m) のコストがかかります。挿入専用のワークロードであれば、特殊なオンラインデータ構造を用いて橋の情報を維持できます。任意の追加と削除がある場合は、より一般的な動的連結性（dynamic connectivity）の設計が必要です。手法を選択する前に、更新の種類、クエリ頻度、整合性の要件を確認してください。
フォローアップ 5: 単純な探索を繰り返すベースラインが依然として優れた回答となるのはどのような場合ですか？
極小のグラフ、特定の疑わしいエッジが 1 本だけある場合、あるいはレイテンシよりもシンプルさが最優先される診断コードなどでは、1 本のエッジを除外して BFS を実行する方がコードが短く、検証も容易です。1 本のエッジに対して O(n + m) のコストがかかることを明記した上で、課題がすべての橋の検出や繰り返しのクエリを求めていない限り、low-link の状態管理を導入しないのが適切です。