強連結成分分解

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