強連結成分分解
SCC, Strongly Connected Components
リファレンス
code: SCC.py
# (参考)@kawap23 / Pythonで強連結成分分解するのにscipyが高速に動く(らしい)話
"""
G: グラフ
O(V + E)
強連結成分数と,各頂点がどこに属すかを返す
"""
N = len(G)
RG = [[] for _ in range(N)]
for i in range(N):
def dfs(v):
while stack:
flag = True
flag = False
stack.append(i)
break
stack.pop()
vs.append(tmp)
def rdfs(v, k):
while stack:
stack.pop()
stack.append(i)
for i in range(N):
dfs(i)
k = 0
rdfs(i, k)
k += 1