Минимальное время, необходимое для окрашивания всех ребер Дерева
Учитывая массив пар 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)