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

"ПОИСК В ШИРИНУ НА ОРГРАФЕ" Условие: В ориентированном графе найти расстояние от вершины A до всех остальных (если путь существует).

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

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)  # только от x к y, не добавляем обратно!

dist = [-1] * (n + 1)
queue = [a]
dist[a] = 0
idx = 0

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

for i in range(1, n + 1):
    if dist[i] != -1:
        print(f"От {a} до {i}: {dist[i]}")
    else:
        print(f"От {a} до {i}: недостижимо")

Загрузка...

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

💬

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

Печать