Длина самой длинной возрастающей последовательности узлов в данном графе

Учитывая корень графа, задача состоит в том, чтобы найти длину самой длинной возрастающей последовательности в графе.

Пример:

Input:   root =     7—-17
                         /    
        1—-2—-5      4
             /                
          11           6—-8
                               /
                            12
Output: 6 
Explanation: The longest increasing sequence in the graph consists of the nodes 1, 2, 5, 6, 8, 12

Input:   2
           /  
        3     1
      /        
    5           6
Output: 4

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

• Примените поиск в глубину к корневому узлу, чтобы посетить и сохранить все узлы в списке.
• Используйте рекурсию для применения поиска в глубину к каждому непосещенному узлу графа и используйте хэш-карту для хранения посещенных узлов графа, сопоставленных с самым длинным путем, заканчивающимся этим узлом.
  • В каждом узле итерации через ArrayList соседей и использование рекурсии на соседних узлах со значением меньше, чем значение текущего узла, и вычисление самого длинного пути, заканчивающегося на них.
  • Найдите максимум самого длинного пути, заканчивающегося к соседям, и добавьте к нему 1 для вычисления самого длинного пути, заканчивающегося к текущему узлу.
• Возвращает максимум всех самых длинных путей

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

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