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

Максимальное количество последовательно соединенных бусинок присутствует в полученной фигуре.

def find_farthest(start, graph, n):
    dist = [-1] * (n + 1)
    dist[start] = 0
    queue = [start]
    while queue:
        v = queue.pop(0)
        for neighbor in graph[v]:
            if dist[neighbor] == -1:
                dist[neighbor] = dist[v] + 1
                queue.append(neighbor)
    farthest = start
    max_dist = 0
    for i in range(1, n + 1):
        if dist[i] > max_dist:
            max_dist = dist[i]
            farthest = i
    return farthest, max_dist
n = int(input())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
farthest_from_1, _ = find_farthest(1, graph, n)
_, distance = find_farthest(farthest_from_1, graph, n)
result = distance + 1
print(result)

Загрузка...

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

💬

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

Печать