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

"ПОИСК В ШИРИНУ С ПОДСЧЁТОМ УРОВНЕЙ" Условие: Вывести все вершины графа по уровням (сначала вершины на расстоянии 0, потом на расстоянии 1, потом на расстоянии 2 и т.д.)

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)

dist = [-1] * (n + 1)
queue = [1]
dist[1] = 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)

# Группируем вершины по расстоянию
max_dist = max(dist[1:])
levels = [[] for _ in range(max_dist + 1)]

for i in range(1, n + 1):
    if dist[i] != -1:
        levels[dist[i]].append(i)

for level in range(max_dist + 1):
    print(f"Уровень {level}:", levels[level])

Загрузка...

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

💬

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

Печать