サイクル検出(DFS)

2022年12月18日

説明

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'