問題
$N$ 頂点 $M$ 辺の有向グラフが与えられる。頂点は $0$ から $N-1$ で番号付けされている。
Gabow のアルゴリズムは、Tarjan の低リンク値（lowlink）を使う方式とは異なり、2本のスタック（訪問済み頂点を積む「パススタック」$S$ と、SCC候補の境界を管理する「境界スタック」$P$）だけを使って強連結成分分解を行う path-based な手法である。
以下の手順で $N$ 頂点すべてを起点に深さ優先探索を行い、各頂点に SCC 番号を割り当てよ。
- 頂点 $v$ を訪問する際、$S,P$ 両方に $v$ を積み、行きがけ順の番号（preorder）を記録する
- $v$ から辺 $(v, w)$ をたどる際: $w$ が未訪問なら再帰的に訪問。$w$ が訪問済みでSCC番号未確定なら、$P$ の頂点のうち preorder が $w$ より大きいものをすべて $P$ から取り除く
- $v$ の子の処理をすべて終えた時点で $P$ の一番上が $v$ 自身であれば、$P$ から $v$ を取り除き、$S$ から $v$ が出てくるまで pop し続け、pop した頂点すべてに同じ SCC 番号を割り当てる（確定した順に $0,1,2,\dots$）
DFS は頂点 $0,1,\dots,N-1$ の順で未訪問なら開始し、隣接頂点は入力で辺が与えられた順にたどる。SCC の個数と各頂点のSCC番号を出力せよ。
入力形式
N M
u_1 v_1
:
u_M v_M制約
入出力例
入力例1
6 7
0 1
1 2
2 0
1 3
3 4
4 5
5 3出力例1
2
1 1 1 0 0 0入力例2
3 2
0 1
1 2出力例2
3
2 1 0概念図
ヒント（段階的開示）
ヒント1（方向性）
Tarjan のアルゴリズムは各頂点に lowlink 値（自分自身または子孫からの後退辺でたどり着ける最小 preorder 値）を持たせて管理する。Gabow の方式はこれを明示的な値として持たず、「境界スタック $P$」という補助スタックの中に「まだ確定していない SCC の境界候補」を preorder の降順に保持することで、同じ情報を間接的に表現する。$P$ の中身を出し入れするだけで lowlink 計算と同じ効果が得られる点がこのアルゴリズムの本質である。
ヒント2（アプローチ）
$P$ に積まれている頂点の preorder は常に下から上へ単調増加になるように保たれる。後退辺 $(v,w)$（$w$ がまだ SCC 未確定の既訪問頂点）を見つけたとき、「$w$ より新しく積まれた境界候補はすべて、今回発見した後退辺によって $w$ と同じ SCC に吸収されうる」ため、$P$ から pop してよい。$v$ の探索が終わった時点で $P$ の最上位が $v$ 自身であれば、それは「$v$ を境界とする SCC が確定した」ことを意味する。
ヒント3（誘導）
preorder = [-1]*n
comp = [-1]*n
idx = 0
comp_count = 0
S, P = [], []
def dfs(v):
global idx, comp_count
preorder[v] = idx; idx += 1
S.append(v); P.append(v)
for w in adj[v]:
if preorder[w] == -1:
dfs(w)
elif comp[w] == -1:
while preorder[P[-1]] > preorder[w]:
P.pop()
if P[-1] == v:
P.pop()
while True:
w = S.pop()
comp[w] = comp_count
if w == v:
break
comp_count += 1$N \le 10^5$ では再帰が深くなりうるため、模範解答ではジェネレータを使った反復DFSに書き換えている（挙動は上記の再帰版と完全に一致する）。
模範解答 (Python)
import sys
def main():
input_data = sys.stdin.read().split()
idx_ptr = 0
n = int(input_data[idx_ptr]); idx_ptr += 1
m = int(input_data[idx_ptr]); idx_ptr += 1
adj = [[] for _ in range(n)]
for _ in range(m):
u = int(input_data[idx_ptr]); idx_ptr += 1
v = int(input_data[idx_ptr]); idx_ptr += 1
adj[u].append(v)
preorder = [-1] * n
comp = [-1] * n
idx_counter = 0
comp_count = 0
S = []
P = []
for start in range(n):
if preorder[start] != -1:
continue
stack = [(start, iter(adj[start]))]
preorder[start] = idx_counter; idx_counter += 1
S.append(start)
P.append(start)
while stack:
v, it = stack[-1]
advanced = False
for w in it:
if preorder[w] == -1:
preorder[w] = idx_counter; idx_counter += 1
S.append(w)
P.append(w)
stack.append((w, iter(adj[w])))
advanced = True
break
elif comp[w] == -1:
while preorder[P[-1]] > preorder[w]:
P.pop()
if advanced:
continue
stack.pop()
if P[-1] == v:
P.pop()
while True:
w = S.pop()
comp[w] = comp_count
if w == v:
break
comp_count += 1
out = []
out.append(str(comp_count))
out.append(' '.join(map(str, comp)))
print('\n'.join(out))
main()Step-by-Step 解説
$S$（パススタック）は現在のDFS経路上でまだSCC未確定の頂点すべてをpreorder順に保持する。$P$（境界スタック）は $S$ の部分集合で、「今後SCCの境界（根）になりうる候補」をpreorderの狭義単調増加を保ったまま保持する。
$(v,w)$ が後退辺（$w$がスタック上）のとき、$w$より後に発見された境界候補はすべて、この閉路によって$w$と同一SCCに吸収されうるため$P$から取り除いてよい。
$v$の子孫の探索が終わった時点で$P$の最上位が$v$自身のままなら、「$v$を根とする閉じたSCCが確定した」ことを意味し、$S$から$v$まで popした頂点集合が1つのSCCになる。
SCCは確定した順（＝DFSの帰りがけで根が見つかった順）に番号付けられ、これは縮約DAGの逆トポロジカル順序に一致する。
DFSは各頂点・各辺を定数回しか処理しないため$O(N+M)$。$N$が大きいとPythonの再帰はスタックオーバーフローするため、模範解答は反復DFS（ジェネレータ保持）に書き換えている。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
$P$から pop する条件を >= にしてしまう | 「preorder が $w$ 以上」を誤って含めてしまう | 正しくは preorder[P[-1]] > preorder[w] の間だけ pop（$w$自身は残す） |
| SCC番号を確定した逆順で振ってしまう | 直感的に「source側から0」と振りたくなる | 本問の仕様では確定した順（sink側から）に $0,1,2,\dots$ と振る |
| 再帰版をそのまま提出しRecursionErrorになる | $N$が大きいケースを想定していない | 反復DFS（スタック+ジェネレータ）に書き換える |
| 自己ループ辺の特別扱いをしてしまう | Tarjan法のlowlink実装の癖を持ち込む | 自己ループも通常の後退辺として自然に処理される |
| 隣接リストをsetで管理し順序を失う | 出力の再現性を軽視する | 入力順を保持するためlistを使う |
次のステップ
- 発展: SCC番号列を使って縮約グラフ（各SCCを1頂点としたDAG）を構築し、トポロジカルソートせよ。SCC番号が確定順（＝逆トポロジカル順）であることを利用すると、追加のソートなしで縮約DAGのトポロジカル順序が得られることを確認せよ。
- 発展2: Tarjanのアルゴリズム（lowlink方式）で同じグラフを処理し、SCCの集合としての分割結果が完全一致することを確認せよ（番号の割り当て方は異なってよい）。