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

Дан набор из 10 ⁹ узлов. Имеется N двунаправленных соединений, и i ^-е соединение соединяет узлы A _{i ^th} и B _{i ^th} . Начиная с первого узла, найти максимальное значение узла, которое может быть достигнуто с использованием заданных соединений.

Примеры:

Input:  N = 4
1  4
4  6
4  10
7  3
Output: 10
Explanation: Move from 1^st node to 4^th node using connection 1, then move to 10^th node from 4^th node using connection 3.

Input:  N = 3
5   6
6   70
70  800
Output:  1
Explanation: You are initially on node 1 and there is no connection from the 1^st node so you can’t reach anywhere.

Подход: Задача может быть решена с помощью DFS на основе следующей идеи.

The idea/intuition is to start from 1^st node and check the nodes we can reach from it directly or through any connected path. Build a graph of nodes where connections connect any two floors, then run dfs and update maximum at each step. 

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Создайте неупорядоченную карту для маркировки соединений между узлами.
• Создайте набор, который покажет, посещался ли узел ранее при обходе dfs.
• Запустите обход dfs с узла 1, пометьте текущий узел как посещенный в наборе и обновите максимум текущим узлом.
• Пройдите по всем дочерним узлам текущего узла, если дочерний узел не посещается, вызовите dfs для дочернего узла.
• Наконец, когда все связанные узлы пройдены, у нас есть максимальный узел, достижимый в res .

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

Выход:

10

Временная сложность: O(V + E), где V — количество вершин, а E — количество ребер в графе.
Вспомогательное пространство: O(V), так как требуется дополнительный посещенный массив размера V.

Статьи по Теме:

• Введение в график — учебные пособия по структурам данных и алгоритмам
• Поиск в глубину или DFS для графика