閉路探索

前回の記事で、解説みると、奇数長の閉路を探索する必要があることがわかった。 閉路の検出ってどうやるんだっけなぁって思って調べた。

inzkyk.github.io

わかりやすい。擬似コードも載ってる。確認する。

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|)になる。引数に長さを足せば、長さを求めることができる。