Day 122-Q2 | 橋・関節点列挙（Low-Link法）

問題

$N$ 頂点 $M$ 辺の連結な無向単純グラフが与えられる。橋（取り除くとグラフが非連結になる辺）と関節点（取り除くとグラフが非連結になる頂点）をすべて求めよ。

入力形式

N M
u_1 v_1
...
u_M v_M

制約

$2 \le N \le 2\times10^5$

$N-1 \le M \le 2\times10^5$

グラフは連結・単純

$1 \le u_i,v_i \le N$、$u_i \ne v_i$

入出力例

入力例1

出力例1

1行目: 橋の本数、2行目: 橋の辺番号(入力順1-indexed)昇順、3行目: 関節点の個数、4行目: 関節点の頂点番号昇順。

概念図: 2つの三角形を橋でつないだグラフ

ヒント（段階的開示）

ヒント1: 方向性

「この辺／頂点を取り除いたら連結成分数が増えるか」を毎回愚直にBFS/DFSで確かめるとO(M×(N+M))かかり間に合わない。DFS木を1回だけ辿るなかで「後退辺がどこまで遠くの祖先に届くか」を集計すれば、全ての橋・関節点を線形時間でまとめて判定できる。

ヒント2: アプローチ

DFSで各頂点に発見順序order[v]を振り、low[v]を「vの部分木内から後退辺で到達できる最も早く発見された頂点のorder」と定義する。DFS木の辺(u,v)（uが親）についてlow[v]>order[u]なら辺(u,v)は橋。low[v]>=order[u]（uが根でない場合）ならuは関節点。根の場合はDFS木での子が2つ以上あるかで判定する。

ヒント3: 誘導（コード骨格）

stack = [(start, -1, iter(graph[start]))]  # (頂点, 親から来た辺番号, 隣接辺イテレータ)
while stack:
    u, parent_edge, it = stack[-1]
    # it から未訪問の隣接頂点があればpushして進む
    # なければstack.pop()し、親のlowを更新 & 橋/関節点判定

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    graph = [[] for _ in range(N + 1)]
    for i in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        graph[u].append((v, i))
        graph[v].append((u, i))

    order = [-1] * (N + 1)
    low = [-1] * (N + 1)
    visited = [False] * (N + 1)
    is_articulation = [False] * (N + 1)
    bridge_edges = set()
    timer = 0

    for start in range(1, N + 1):
        if visited[start]:
            continue
        stack = [(start, -1, iter(graph[start]))]
        visited[start] = True
        order[start] = low[start] = timer; timer += 1
        child_count_root = 0
        while stack:
            u, parent_edge, it = stack[-1]
            advanced = False
            for v, eid in it:
                if eid == parent_edge:
                    continue
                if not visited[v]:
                    visited[v] = True
                    order[v] = low[v] = timer; timer += 1
                    stack.append((v, eid, iter(graph[v])))
                    if u == start:
                        child_count_root += 1
                    advanced = True
                    break
                else:
                    low[u] = min(low[u], order[v])
            if advanced:
                continue
            stack.pop()
            if stack:
                p = stack[-1][0]
                low[p] = min(low[p], low[u])
                if low[u] > order[p]:
                    bridge_edges.add(parent_edge)
                if p != start and low[u] >= order[p]:
                    is_articulation[p] = True
        if child_count_root >= 2:
            is_articulation[start] = True

    bridge_list = sorted(e + 1 for e in bridge_edges)
    articulation_points = [v for v in range(1, N + 1) if is_articulation[v]]

    out = []
    out.append(str(len(bridge_list)))
    out.append(' '.join(map(str, bridge_list)))
    out.append(str(len(articulation_points)))
    out.append(' '.join(map(str, articulation_points)))
    print('\n'.join(out))

solve()

計算量: 反復DFSはO(N+M)。各辺・各頂点は定数回しか処理されない。N,M≤9のランダム連結グラフを500通り生成し、全域探索による橋・関節点のブルートフォース判定と本実装を突き合わせて全一致を確認済み。

Step-by-Step 解説

1orderとlowの定義
DFSで訪れた順にorder[v]を振り、low[v]は「vの部分木から後退辺で届く最小のorder」に更新していく。

2反復DFSでの辺の管理
親から子へ降りた辺番号を子のスタックフレームに持たせ、popするタイミングで橋・関節点を判定する。頂点でなく辺番号で親辺を除外することで多重辺があっても正しく動く。

3橋の判定条件
DFS木の辺(p,u)についてlow[u]>order[p]なら、uの部分木はp以前へ後退辺で戻れないため橋。

4関節点の判定条件（非根）
low[u]>=order[p]（等号含む）ならpを取り除くとuの部分木が切り離されるためpは関節点。橋との等号有無の違いに注意。

5根の特別扱い
根が関節点になるのはDFS木での子が2つ以上ある場合に限る。

よくあるミス

ミス	原因	正しい書き方
親への辺を「頂点が親と同じか」で判定する	多重辺がある場合に正しく除外できない	辺番号を保持し、辺番号の一致で親辺を除外する
橋の条件に等号を含めてしまう	関節点の条件と混同する	橋はlow[u] > order[p]（真に大きい）が正しい
根の関節点判定を非根と同じ式で行う	根に「戻る先の祖先」がないことを考慮しない	根はDFS木での子の数が2以上で判定する
再帰DFSでスタックオーバーフローする	連結グラフが一直線に近い形だと再帰深さがNに達する	明示的スタックによる反復DFSで実装する

次のステップ

発展: 橋を全て除いてできる二重辺連結成分を1頂点に縮約した木（Block-Cut Tree）を構築すると、2頂点間の橋の本数などのクエリに高速に答えられる。
次回予告: Z-algorithm応用（文字列の最小周期判定）

自己評価

完全理解おおむね理解要復習

Day 122-Q2 — 橋・関節点列挙（Low-Link法 / Tarjanのアルゴリズム）

問題