強連結成分を縮めてDAGにする
有向グラフで相互に到達できる頂点を1つの成分にまとめます。成分を縮約したグラフには有向閉路がありません。
言語：Python / 計算量：発展実装 O(V+E)、基準検証 O(V(V+E))
考え方
- 1回目のDFSで帰りがけ順を記録。
- すべての辺を逆にします。
- 帰りがけ順の逆から逆グラフを探索し、成分番号を付けます。
具体例
0→1、1→0、1→2 なら {0,1} と {2}。縮約後は成分A→成分BのDAGです。
実装
g=[[1],[0,2],[]]
# この小例を到達可能性で確かめる
def reach(s):
seen={s};stack=[s]
while stack:
v=stack.pop()
for u in g[v]:
if u not in seen:seen.add(u);stack.append(u)
return seen
r=[reach(v) for v in range(3)]
print(1 in r[0] and 0 in r[1])注意する条件
一方向の到達では同じ成分になりません。短い確認例は全始点探索。線形時間の実装は講義後半に掲載。
確認問題
例の強連結成分の個数は？
解答と理由
2
0と1は相互到達でき、2からは戻れません。
実装課題
小さい有向グラフで相互到達する頂点の組 i<j の数を求める。N≤80、M≤1000。N M と有向辺（0始まり）。全始点探索でよい。
入力:
3 3
0 1
1 0
1 2
出力:
1参考実装
n,m=map(int,input().split());g=[[] for _ in range(n)]
for _ in range(m):
u,v=map(int,input().split());g[u].append(v)
r=[]
for s in range(n):
seen={s};stack=[s]
while stack:
v=stack.pop()
for u in g[v]:
if u not in seen:seen.add(u);stack.append(u)
r.append(seen)
print(sum(j in r[i] and i in r[j] for i in range(n) for j in range(i+1,n)))線形時間のSCC実装へ進む
帰りがけ順とは、ある頂点から行ける未探索の枝をすべて探索し終えたときに、その頂点を記録する順序です。先にスタックから取り出す順とは異なります。下の実装では (頂点, 次に見る辺の番号) を保存し、再帰から戻る動きを再現します。
逆グラフで帰りがけ順の逆から探索すると、まだ分類していない頂点のうち、ひとつの強連結成分だけを取り出せます。成分を縮約したDAGの順序と、2回目の探索方向が対応するためです。
すべての頂点と辺を各パスで定数回処理するので O(V+E)。戻り値 comp[v] は頂点vの成分番号、countは成分数です。番号が同じかどうかで相互到達を判定できます。
def scc(g):
n = len(g)
rg = [[] for _ in range(n)]
for v in range(n):
for u in g[v]:
rg[u].append(v)
seen = [False] * n
order = []
for s in range(n):
if seen[s]:
continue
seen[s] = True
stack = [(s, 0)]
while stack:
v, i = stack[-1]
if i == len(g[v]):
order.append(v)
stack.pop()
else:
stack[-1] = (v, i + 1)
u = g[v][i]
if not seen[u]:
seen[u] = True
stack.append((u, 0))
comp = [-1] * n
count = 0
for s in reversed(order):
if comp[s] != -1:
continue
comp[s] = count
stack = [s]
while stack:
v = stack.pop()
for u in rg[v]:
if comp[u] == -1:
comp[u] = count
stack.append(u)
count += 1
return comp, count
print(scc([[1], [0, 2], []]))