サイクル検出(DFS)
説明
DFSしながら訪問直後はその頂点を「処理中」としておき、DFSの途中で「処理中」ノードに到達したらサイクルがあったことになる。
WHITE = 0 # 未訪問
GRAY = 1 # 処理中
BLACK = 2 # 処理完了
def dfs(u, graph, color):
# DFSしながらサイクルを検出したら True を返す
color[u] = GRAY
for v in graph[u]:
if color[v] == GRAY:
return True
elif color[v] == BLACK:
continue
if dfs(v, graph, color):
return True
color[u] = BLACK
return False
def solve(n,m,graph):
color = [WHITE for _ in range(n)]
for i in range(n):
if color[i] == WHITE:
loop = dfs(i, graph, color)
if loop:
return 'Yes'
return 'No'Python