Минимальное время, необходимое для окрашивания всех ребер Дерева

Опубликовано: 22 Сентября, 2022

Учитывая массив пар Edges[][] , представляющих ребра, соединяющие вершины в Дереве, состоящем из N узлов, задача состоит в том, чтобы найти минимальное время, необходимое для окрашивания всех ребер Дерева, исходя из предположения, что для окрашивания ребра требуется 1 единица времени.

Примечание. Несколько ребер могут быть окрашены в определенный момент времени, но узел может быть частью только одного из ребер, окрашенных в определенный день.

Примеры

Input: Edges[][] = ((1, 2), (3, 4), (2, 3))

Output: 2
Explanation: 
Step 1: Color edges (1, 2) and (3, 4)
Step 2: Color edge (2, 3) 

Input: Edges[][] = ((1, 2), (1, 3), (1, 4))

Output : 3

Подход: Эту проблему можно решить с помощью DFS (поиск в глубину). Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте глобальные переменные, скажем , как 0, чтобы сохранить минимальное время, необходимое для окрашивания всех ребер дерева.
  • Инициализируйте переменную current_time как 0, чтобы сохранить время, необходимое для окрашивания текущего ребра.
  • Переберите дочерние элементы текущего узла и выполните следующие шаги:
    • Если текущее ребро не посещается, т.е. текущий узел не равен родительскому узлу:
      • Увеличьте текущее_время на 1 .
      • Проверьте, был ли родительский край окрашен в то же время или нет. Если окажется, что это правда, то увеличьте current_time на 1 , так как узел не может быть частью более чем одного ребра, которые окрашиваются одновременно.
      • Обновить ответ как максимум ответов и текущего_времени.
      • Вызовите рекурсивную функцию minTimeToColor для дочерних элементов текущего узла.
  • После завершения этой функции выведите ans .

Ниже приведен код для вышеуказанного подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ