Day 132-Q5 | Robbinsの定理による強連結有向化

問題

$N$頂点$M$辺の連結な単純無向グラフが与えられる。このグラフには橋（取り除くとグラフが非連結になる辺）が1本も存在しないことが保証されている。

各辺にちょうど1つの向きを付けて有向グラフを作り、強連結（どの2頂点間にも有向路が存在する）にせよ。頂点1からDFSし、木辺は親→子、後退辺は子孫→祖先へ向ける構成法に従った出力を採点基準の一例として示す。

入力形式

N M
u_1 v_1
...
u_M v_M

制約

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

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

連結かつ橋を持たない（2-辺連結）ことが保証

入出力例

入力例1

出力例1

頂点1からDFSし入力の辺の出現順で探索。1→2→3→4→5が木辺、5→1は後退辺、非木辺1-3は3の深さが深いため3→1になる。

概念図

ヒント（段階的開示）

ヒント1（方向性）

橋になっている辺はどちらの向きにしても戻る経路が存在しないため、橋があると強連結にはできない。逆に橋がなければ必ず強連結にできる、というのがRobbinsの定理（1939）の主張である。

ヒント2（アプローチ）

頂点1からDFSする。木辺（未訪問頂点へ進む辺）は「親→子」に固定する。木辺以外は必ず「今の頂点の祖先」に向かう後退辺になる（無向グラフのDFSでは前進辺・横断辺が発生しない）。後退辺は「子孫→祖先」に固定する。この2種類だけで、橋がないグラフ全体が強連結になる。

ヒント3（誘導）

def dfs(u, parent_edge):
    visited[u] = True
    disc[u] = timer[0]; timer[0] += 1
    for v, eid in adj[u]:
        if eid == parent_edge or eid in direction:
            continue
        if not visited[v]:
            direction[eid] = (u, v)      # 木辺: 親→子
            dfs(v, eid)
        elif disc[v] < disc[u]:
            direction[eid] = (u, v)      # 後退辺: 子孫→祖先

模範解答 (Python)

import sys
from collections import defaultdict

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    edges = []
    adj = defaultdict(list)
    for i in range(m):
        u = int(data[idx]); v = int(data[idx + 1]); idx += 2
        edges.append((u, v))
        adj[u].append((v, i))
        adj[v].append((u, i))

    visited = [False] * (n + 1)
    disc = [0] * (n + 1)
    direction = [None] * m

    timer = 0
    stack = [(1, -1, iter(adj[1]))]
    visited[1] = True
    disc[1] = timer; timer += 1
    while stack:
        u, pe, it = stack[-1]
        advanced = False
        for v, eid in it:
            if eid == pe or direction[eid] is not None:
                continue
            if not visited[v]:
                direction[eid] = (u, v)
                visited[v] = True
                disc[v] = timer; timer += 1
                stack.append((v, eid, iter(adj[v])))
                advanced = True
                break
            elif disc[v] < disc[u]:
                direction[eid] = (u, v)
        if not advanced:
            stack.pop()

    out = []
    for i in range(m):
        a, b = direction[i]
        out.append(f"{a} {b}")
    print("\n".join(out))

solve()

Step-by-Step 解説

1DFS木の性質
無向グラフのDFSでは木辺と後退辺の2種類しか現れない（前進辺・横断辺は存在しない）。

2木辺は親→子、後退辺は子孫→祖先
根から任意の頂点へは木辺で到達でき、任意の頂点から根へは後退辺でショートカットして戻れる。

3橋がないことの意味
すべての木辺は、その部分木の中に少なくとも1本、部分木の外へ出る後退辺を持つ。これが橋の不在の定義そのものと対応する。

4強連結性の証明の骨子
任意の2頂点x,yについて、xから根へ戻る経路（木辺+後退辺ショートカット）とyへの木辺経路をつなげば有向路が構成できる。

5計算量
DFSはO(N+M)。反復DFS（スタック+イテレータ再開）にすることでNが大きい場合のスタックオーバーフローを回避する。

よくあるミス

ミス	原因	正しい書き方
前進辺・横断辺があると誤解する	有向グラフのDFS分類をそのまま無向グラフに当てはめる	無向グラフでは前進辺・横断辺は原理的に発生しないと理解し木辺と後退辺の2分岐で実装する
同じ辺を2回処理し向きが矛盾する	辺にIDを振らず隣接リストの往復だけで判定する	各辺にID(eid)を振り`direction[eid] is not None`で確定済みをスキップ
親の辺を後退辺として再度たどる	`if eid==pe: continue`を入れ忘れる	DFSで今来た辺のIDを渡し、その辺だけ特別にスキップする
再帰DFSでスタックオーバーフロー	Nが大きい一直線に近い木構造で再帰が深くなる	明示的スタック+イテレータの一時停止・再開パターンで反復DFSに書き換える

次のステップ

発展: 橋を含むグラフでは全体を強連結にできないが、各2-辺連結成分ごとに強連結有向化し橋は任意の向きに固定する部分的構成への一般化
発展2: 頂点連結度2以上（2-点連結）のグラフの強連結有向化（st-numberingを用いる、より難しい構成）
次回予告: 次回のテーマは今後のセッションで選定

自己評価

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

Day 132-Q5 — Robbinsの定理による強連結有向化（Strong Orientation）

問題