Day 008-Q2 | 強連結成分分解（SCC）

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる。強連結成分の個数と、各頂点が属する SCC の番号（トポロジカル順）を求めよ。

制約

$1 \le N \le 10^5$

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

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

入出力例

入力例 1

出力例 1

3
0 0 0 1 2 2

ヒント (段階的開示)

ヒント1: 方向性

Kosaraju のアルゴリズムを使う。2回の DFS で SCC を分解。

ヒント2: アプローチ

1回目 DFS: 帰りがけ順でスタックに頂点を積む。
2回目 DFS: 逆辺グラフで、スタックから取り出す順に DFS。

ヒント3: 誘導

$N = 10^5$ 規模では再帰がスタックオーバーフローしうるため、反復DFSに変換。

模範解答 (Python)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(200010)

def solve():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    rev_graph = [[] for _ in range(N + 1)]

    for _ in range(M):
        u, v = map(int, input().split())
        graph[u].append(v)
        rev_graph[v].append(u)

    visited = [False] * (N + 1)
    order = []

    def dfs1(start):
        stack = [(start, 0)]
        while stack:
            v, idx = stack.pop()
            if idx == 0:
                if visited[v]:
                    continue
                visited[v] = True
                stack.append((v, 1))
                for u in graph[v]:
                    if not visited[u]:
                        stack.append((u, 0))
            else:
                order.append(v)

    for v in range(1, N + 1):
        if not visited[v]:
            dfs1(v)

    comp = [-1] * (N + 1)
    label = 0

    def dfs2(start, lbl):
        stack = [start]
        while stack:
            v = stack.pop()
            if comp[v] != -1:
                continue
            comp[v] = lbl
            for u in rev_graph[v]:
                if comp[u] == -1:
                    stack.append(u)

    for v in reversed(order):
        if comp[v] == -1:
            dfs2(v, label)
            label += 1

    print(label)
    print(*[comp[v] for v in range(1, N + 1)])

solve()

Step-by-Step 解説

11回目 DFS（帰りがけ順記録）
全頂点から DFS、探索完了時に order スタックへ追加。反復DFSで実装。

2逆辺グラフ構築
全辺 $u \to v$ を $v \to u$ に反転。

32回目 DFS（SCC 分解）
order を逆順に取り出し、逆グラフで DFS。同 DFS で到達できる頂点群 = 1つの SCC。

よくあるミス

ミス	原因	正しい書き方
再帰 DFS によるスタックオーバーフロー	$N=10^5$ 規模で限界	反復 DFS
帰りがけ順の記録ミス	「訪問時」ではなく「完了時」に append	`(v, 1)` パターンで帰りがけを模倣

次のステップ

発展問題: 2-SAT（SCC + トポロジカル順で解く充足可能性問題）

自己評価

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

Day 008-Q2 — 強連結成分分解（SCC）

問題

制約