dfs-閉ループの検出について
概要
dfsを用いた閉ループの検出- より狭い用語の使用法では、トポロジカルソートを行った際に、フラグ管理をすることで閉ループを検出できる
- dfsで次のノードに行く前に、
tempフラグを利用し、探索が完了したらcompleteフラグに設定するtempフラグのノードを見つけたら閉ループが存在することになる
union-findを用いた閉ループの検出- すべてのグラフの定義をunion-findのunionしていき、結合しようとした段階で、すでに同じ親を持っている場合、閉ループが存在する
union-findを用いた閉ループの検出
import collections
class UnionFind:
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def solve(n: int, edges: List[List[int]]):
G = collections.defaultdict(list)
uf = UnionFind(n)
for a, b in edges:
if uf.find(a) == uf.find(b):
return False
uf.union(a, b)
return True and len(edges) == n-1
dfsの具体例
from collections import defaultdict
from enum import Enum
class Status(Enum):
NOT_STARTED = 0
TMP_CHECKED = 1
COMPLETED = 2
def dfs(G, pos, vis):
if vis[pos] == Status.TMP_CHECKED:
"""
ここが一致すると、閉ループがあることになる
"""
return False
elif vis[pos] == Status.NOT_STARTED:
vis[pos] = Status.TMP_CHECKED
rets = []
for npos in G[pos]:
if vis[npos] != Status.COMPLETED:
rets.append(dfs(G, npos, vis))
vis[pos] = Status.COMPLETED
return all(rets)
return True
def solve(num, prereqs):
G = defaultdict(list)
for a, b in prereqs:
G[b].append(a)
vis = defaultdict(lambda :Status.NOT_STARTED)
return all([dfs(G, i, vis) for i in list(G.keys())])
assert solve(num = 2, prereqs = [[1,0]]) == True
assert solve(num = 2, prereqs = [[1,0],[0,1]]) == False