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

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

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)
    graph[b].append(a)

visited = [False] * (n + 1)
cycle_found = False

def dfs(v, parent):
    global cycle_found
    visited[v] = True
    for to in graph[v]:
        if not visited[to]:
            dfs(to, v)
        elif to != parent:
            cycle_found = True

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

print(cycle_found)

Загрузка...

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

💬

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

Печать