ループをまとめる
ある時点からループするような構造があるとき、ループ部分をひとかたまりとしてまとめて処理することで計算量を削減できる。
code: Loop_tail_decomposition.py
from collections import deque
def Loop_tail_decomposition(s, A):
"""
s = 開始位置
A = 次に訪問する頂点配列(子リスト)
ある地点からループする構造を、ループに含まれない部分(Tail)とループ(Loop)に分解する
"""
Loop = deque()
D = {} # 探索済み頂点
nxt = s
while True:
if nxt in D: break
Loop.append(nxt)
nxt = Anxt # 次の地点を指定。なにか計算が必要ならここを変える Tail = []
Tail.append(Loop.popleft())
Loop = list(Loop)
return Tail, Loop