Статья Автор: Дубинин Дмитрий

ПОИСК ЦИКЛА В ОРИЕНТИРОВАННОМ ГРАФЕ

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

visited = [0] * (n + 1)  # 0 - не посещена, 1 - в процессе, 2 - обработана
cycle_found = False

def dfs(v):
    global cycle_found
    visited[v] = 1
    for to in graph[v]:
        if visited[to] == 0:
            dfs(to)
        elif visited[to] == 1:
            cycle_found = True
    visited[v] = 2

for i in range(1, n + 1):
    if visited[i] == 0:
        dfs(i)

print(cycle_found)

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать