Войти
или
Зарегистрироваться
Маркетплейс
Курсы
Учебник
Учебник 2.0
ОГЭ/ЕГЭ
Олимпиады
Рубрикатор
Компилятор
Онлайн Компилятор
Компилятор Python с отладкой
Питон - Черепашка
Редактор HTML Code
SQLite Studio - работа с БД
Статья Автор:
Дубинин Дмитрий
ПОИСК ЦИКЛА В ОРИЕНТИРОВАННОМ ГРАФЕ
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)
×
Загрузка...
Чтобы оставить комментарий, необходимо авторизоваться
💬
Пока нет комментариев. Будьте первым!
Печать