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

ТОПОЛОГИЧЕСКАЯ СОРТИРОВКА (DFS)

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 - обработана
order = []
has_cycle = False

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

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

if has_cycle:
    print("Сортировка невозможна (есть цикл)")
else:
    print("Топологический порядок:", order[::-1])

Загрузка...

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

💬

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

Печать