なもり分解
なもりグラフから閉路を取り出し、もとのグラフから閉路に含まれる辺を削除する。
削除後のグラフは閉路に含まれる頂点を根とする森になっている。
有向グラフの場合は実装がより簡単になる。
なもり分解（有向グラフ）
code: Namori_decomposition.py
from collections import deque
def Namori_decomposition(N):
"""
N頂点N辺の単純連結無向グラフGから閉路を取り出す
Gに対して破壊的処理
"""
# bfsで後退辺を探す
Q = deque(0)
frm = -1 * N
frm0 = 0
while Q:
x = Q.popleft()
for y in Gx:
if y == frmx: continue
if frmy != -1:
s = x
else:
frmy = x
Q.append(y)
# 後退辺の端点からdfs
frm = -1 * N
frms = N
used = 0 * N
Q = deque(s)
while Q:
x = Q.pop()
if usedx: continue
usedx = 1
for y in Gx:
if y == frmx: continue
if usedy:
s, t = x, y
else:
frmy = x
Q.append(y)
# dfs木を用いて閉路を復元
pos = s
C = pos
while pos != t:
pos = frmpos
C.append(s)
# グラフから閉路に含まれる辺を取り除く
Gs.remove(t)
Gt.remove(s)
while s != t:
Gpos.remove(frmpos)
G[frmpos].remove(pos)
s = frms
return C