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

"ЦЕНТРАЛЬНАЯ ВЕРШИНА" Условие: Найти вершину в графе, максимальное расстояние от которой до любой другой вершины минимально (центр графа).

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)

def bfs_max_dist(start):
    dist = [-1] * (n + 1)
    queue = [start]
    dist[start] = 0
    idx = 0
    max_d = 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)
                if dist[to] > max_d:
                    max_d = dist[to]
    return max_d

center = 1
min_max_dist = bfs_max_dist(1)

for v in range(2, n + 1):
    d = bfs_max_dist(v)
    if d < min_max_dist:
        min_max_dist = d
        center = v

print("Центральная вершина:", center)
print("Радиус графа:", min_max_dist)

Загрузка...

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

💬

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

Печать