Day 141-Q2 | Kosaraju's Algorithm

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる。頂点は $0$ から $N-1$ で番号付けされている。

Kosaraju のアルゴリズムで強連結成分（SCC）分解を行い、各頂点にSCC番号を割り当てよ。出力を一意にするため以下の手順どおりに実装すること。

第1パス（元グラフ上のDFS）

頂点 $0,1,\dots,N-1$ の順に、未訪問なら起点としてDFS。隣接頂点は入力順にたどる
頂点の帰りがけ順に頂点番号を配列 order に追加

第2パス（逆グラフ上のDFS）

orderを末尾から走査し、SCC番号未確定の頂点があれば起点として逆グラフ上でDFS、到達点すべてに同じSCC番号を割り当てる
新しい起点ごとに $0$ から順にSCC番号を割り当てる

入力形式

N M
u_1 v_1
:
u_M v_M

制約

$1 \le N \le 10^5$

$0 \le M \le 2\times10^5$

$0 \le u_i, v_i < N$

入出力例

入力例1

出力例1

2
0 0 0 1 1 1

入力例2

3 2
0 1
1 2

出力例2

3
0 1 2

概念図

ヒント（段階的開示）

ヒント1（方向性）

強連結成分をなす頂点集合は、元グラフでも逆グラフでも「互いに行き来できる」性質が変わらない。Kosarajuのアルゴリズムはこの対称性を使い、「元グラフの帰りがけ順」というトポロジカルソートに近い順序情報を、逆グラフ上でその順序どおりに探索することで、各DFSの到達範囲がちょうど1つのSCCに一致するように仕向けている。

ヒント2（アプローチ）

第1パスで得られるorder（帰りがけ順）はSCCを1頂点に縮約したDAGのトポロジカル順序になっている。これを逆から見ることはDAGをsource側から順に見ていくことに相当する。逆グラフを使うことで、あるSCCの起点から探索したときに「まだ訪問していない、より sink側のSCC」へ誤って侵入することを防ぐ。

ヒント3（誘導）

# 第1パス: 元グラフ、帰りがけ順
visited = [False]*n
order = []
for s in range(n):
    if visited[s]: continue
    stack = [(s, iter(adj[s]))]
    visited[s] = True
    while stack:
        v, it = stack[-1]
        advanced = False
        for w in it:
            if not visited[w]:
                visited[w] = True
                stack.append((w, iter(adj[w])))
                advanced = True
                break
        if advanced:
            continue
        stack.pop()
        order.append(v)   # 帰りがけ

# 第2パス: 逆グラフ、order の逆順
comp = [-1]*n
comp_count = 0
for v in reversed(order):
    if comp[v] != -1: continue
    # v を起点に逆グラフ radj 上で探索し、到達点すべてに comp_count を割り当てる
    ...
    comp_count += 1

模範解答 (Python)

import sys

def main():
    data = sys.stdin.read().split()
    ptr = 0
    n = int(data[ptr]); ptr += 1
    m = int(data[ptr]); ptr += 1
    adj = [[] for _ in range(n)]
    radj = [[] for _ in range(n)]
    for _ in range(m):
        u = int(data[ptr]); ptr += 1
        v = int(data[ptr]); ptr += 1
        adj[u].append(v)
        radj[v].append(u)

    visited = [False] * n
    order = []
    for s in range(n):
        if visited[s]:
            continue
        stack = [(s, iter(adj[s]))]
        visited[s] = True
        while stack:
            v, it = stack[-1]
            advanced = False
            for w in it:
                if not visited[w]:
                    visited[w] = True
                    stack.append((w, iter(adj[w])))
                    advanced = True
                    break
            if advanced:
                continue
            stack.pop()
            order.append(v)

    comp = [-1] * n
    comp_count = 0
    for v in reversed(order):
        if comp[v] != -1:
            continue
        stack = [v]
        comp[v] = comp_count
        while stack:
            x = stack.pop()
            for y in radj[x]:
                if comp[y] == -1:
                    comp[y] = comp_count
                    stack.append(y)
        comp_count += 1

    out = [str(comp_count), ' '.join(map(str, comp))]
    print('\n'.join(out))

main()

Step-by-Step 解説

1第1パスの帰りがけ順が持つ意味
SCCを縮約したDAG上で、帰りがけ順に並べれば「トポロジカル順序」が自然に得られる（あるSCCに属する頂点の帰りがけ時刻は、sink側の別SCCの頂点の帰りがけ時刻より必ず大きい）。

2なぜ逆グラフを使うのか
逆グラフ上で探索することで、進める方向がDAG上で「sourceに向かう」方向に限定され、ちょうど1つのSCCの範囲内で探索が止まる。

3SCC番号の割り当て順序
第2パスで新しい起点が選ばれる順序はDAGのトポロジカル順序（source側から）と一致するため、SCC番号はトポロジカル順に振られる。Gabow法（Day140-Q1）は逆に sink側から番号を振る。

4計算量
第1パス・第2パスともに各頂点・各辺を定数回しか処理しないため全体で$O(N+M)$。

53アルゴリズムの比較
Tarjan法・Gabow法は1回のDFSで済ませるが、Kosaraju法は2回の独立したDFSで済ませる代わりに逆グラフを明示的に構築する必要がある。

よくあるミス

ミス	原因	正しい書き方
`order`を逆順にせず先頭から第2パスを行ってしまう	行きがけ順と帰りがけ順を混同	必ず帰りがけ順で`order`を作り、`reversed(order)`で走査
第2パスで逆グラフではなく元グラフをそのまま使ってしまう	Kosaraju法の核心を見落とす	`radj`を別途構築し第2パスはそちらを使う
第1パスでvisited判定を忘れ、同じ頂点を複数回帰りがけ順に追加	DFS実装のvisited管理を怠る	訪問時に即座に`visited[w]=True`をセット
SCC番号を頂点番号順に割り当ててしまう	「起点になった順」ではなく「頂点番号順」だと誤解	`reversed(order)`でcompが未確定の頂点が現れた順に番号を割り当てる
$N$が大きい場合に再帰DFSを使いRecursionError	反復DFSへの書き換えを怠る	スタック+ジェネレータで反復DFSを実装

次のステップ

発展: 本問の出力（トポロジカル順のSCC番号）を使ってSCCを1頂点に縮約したDAGを構築し、隣接リスト順で出力すればトポロジカルソート済みになっていることを確認せよ。
発展2: Day140-Q1のGabowのアルゴリズムで同じグラフを処理し、SCCの集合としての分割結果が完全一致すること、番号の振られ方が正反対になることを確認せよ。

自己評価

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

Day 141-Q2 — Kosaraju's Algorithm（2パスDFSによる強連結成分分解）

問題