0

Необходимо решить задачу:

Маленький мальчик делает бусы. У него есть много пронумерованных бусинок. Каждая бусинка имеет уникальный номер - целое число в диапазоне от 1 до N. Он выкладывает все бусинки на полу и соединяет бусинки между собой произвольным образом так, что замкнутых контуров не образуется. Каждая из бусинок при этом оказывается соединенной с какой-либо другой бусинкой. Требуется определить, какое максимальное количество последовательно соединенных бусинок присутствует в полученной фигуре.

Входные данные В первой строке входного файла 1 <= N <= 2500 - количество бусинок . В последующих N - 1 строках по два целых числа - номера, соединенных бусинок.

Выходные данные Вывести в файл одно число - искомое количество бусинок.

Примеры входные данные 5 2 1 2 3 2 4 2 5 выходные данные 3

Мой код падает на одном из тестов (run-time error) В чем может быть проблема?

n = int(input())
l = []

for i in range(n - 1):
    l.append([int(i) for i in input().split()])

ways = []


for i in range(n):
    ways.append([])

for el in l:
    x, y = el
    ways[x - 1].append(y - 1)
    ways[y - 1].append(x - 1)

def dfs(graph, start, sum, arrAccum, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    if (graph[start] - visited == set()):
        arrAccum.append(sum)
    else:
        sum += 1
      
    for next in graph[start] - visited:
        dfs(graph, next, sum, arrAccum, visited)


graph = dict.fromkeys(range(n))

for i in range(len(ways)):
    graph[i] = set(ways[i])

node_accum = []
graph_accum = []

for el in range(n):
    node_accum = []
    dfs(graph, el, 1, node_accum)
    graph_accum.extend(node_accum)

print(max(graph_accum))
3
  • Глубина рекурсии превышает 1000. Питон падает с переполнением стека. 16 мар в 20:34
  • В остальном ваш код выглядит рабочим. Сложность n^2. Задачу можно решить за n. 16 мар в 20:36
  • 2
    Неориентированный граф без петель с n вершинами и n-1 ребром - это дерево. Длиннейший путь - его диаметр. Вы решаете задачу поиска диаметра дерева. 16 мар в 20:45

1 ответ 1

0

Если граф является несвязным, то graph_accum будет содержать несколько значений, и функция max() выберет из них максимальное. Однако максимальное количество последовательно соединенных бусинок должно быть определено только наибольшим значением в graph_accum.

Чтобы исправить эту ошибку, замените строку:

print(max(graph_accum))

на

print(max(graph_accum) if graph_accum else 1)

Здесь, если graph_accum пустой (то есть граф несвязный), выводится 1, потому что в этом случае есть по крайней мере одна последовательность из одной бусинки.

1
  • if graph_accum всегда истинно. Даже если нет, это не причина для ошибки времени выполнения. 16 мар в 22:26

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.