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

ТОПОЛОГИЧЕСКАЯ СОРТИРОВКА (BFS - Алгоритм Кана)

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

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

queue = []
for v in range(1, n + 1):
    if indegree[v] == 0:
        queue.append(v)

result = []
idx = 0
while idx < len(queue):
    v = queue[idx]
    idx += 1
    result.append(v)
    for to in graph[v]:
        indegree[to] -= 1
        if indegree[to] == 0:
            queue.append(to)

if len(result) != n:
    print("Сортировка невозможна (есть цикл)")
else:
    print("Топологический порядок:", result)

Загрузка...

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

💬

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

Печать