閉路探索
前回の記事で、解説みると、奇数長の閉路を探索する必要があることがわかった。 閉路の検出ってどうやるんだっけなぁって思って調べた。
わかりやすい。擬似コードも載ってる。確認する。
from collections import defaultdict G = defaultdict(list) N, M = map(int, input().split()) ACTIVE, NEW, FINISHED = (-1, 0, 1) state = [NEW for i in range(N)] for i in range(M): fr, to = map(int, input().split()) G[fr].append(to) # G[to].append(fr) def has_cyclic(pos): global state state[pos] = ACTIVE for to in G[pos]: if state[to] == ACTIVE: return True elif state[to] == NEW: if has_cyclic(to): return True state[pos] = FINISHED return False print(has_cyclic(0))
頂点 0 からの閉路を見ているけど、結合じゃなければ、頂点の状態がNEWのものを探索すればよい。全部探索してるから、O(|N|+|M|)になる。引数に長さを足せば、長さを求めることができる。