なもり分解（有向グラフ） - かに

なもり分解（有向グラフ）

code: Namori_decomposition_directed

P = 0 * N # iから初めてループに入る頂点

L = 0 * N # iが属するループ長

D = 0 * N # iからPiまでの距離

for i in range(N):

if Li != 0: continue

now = i

Li = -1

S = i

while True:

now = Xnow

if Lnow != 0: break

Lnow = -1

S.append(now)

if Lnow < 0:

loop_len = len(S) - S.index(now)

while S:

j = S.pop()

Pj = j

Lj = loop_len

Dj = 0

if j == now: break

for d, j in enumerate(S):

Pj = Pnow

Lj = Lnow

Dj = Dnow + len(S) - d

code: Namori_decomposition_directed2.py

def Namori_decomposition_directed(A):

"""

N頂点N辺の有向グラフ（単純連結でなくてもよい）から閉路を取り出す

Aは Ai := 頂点iから出ている辺の行先

返り値Cyclesは各閉路を要素とする二次元配列

"""

N = len(A)

used = 0 * N

Cycles = []

for i in range(N):

if usedi: continue

S = []

now = i

while not usednow:

S.append(now)

usednow = 1

now = Anow

is_cycle = usednow == 1

if is_cycle:

Cycles.append([])

while S:

s = S.pop()

if is_cycle:

Cycles-1.append(s)

useds = 2

if s == now:

is_cycle = 0

else:

useds = 2

return Cycles