Я имею в виду SkiennaКнига по алгоритмам.

Проблема тестирования ли графG содержитHamiltonian path являетсяNP-hardгде гамильтонов путьP путь, который посещает каждую вершину ровно один раз. Не должно быть ребра в G от конечной вершины до начальной вершины P, в отличие от задачи о гамильтоновом цикле.

Дан ориентированный ациклический граф G (DAG), дайO(n + m) алгоритм времени, чтобы проверить, содержит ли он гамильтонов путь.

Мой подход,

Я планирую использоватьDFS а такжеTopological sorting, Но я нене знаю, как соединить две концепции в решении проблемы. Как можно использовать топологическую сортировку для определения решения.

Какие-либо предложения?