В задаче требуется для заданного ор

В задаче требуется для заданного ориентированного графа найти путь, содержащий
заданное множество вершин.
Для решения задачи рассмотрим конденсацию данного графа — граф, получаю-
щийся из исходного объединением сильно связных компонент в вершины (подробнее
см. в книге Кормена раздел "Сильно связные компоненты"). Если какая-то верши-
на исходного графа входила в множество обязательных для посещения вершин, то
вершина, соответствующая содержащей её компоненте сильной связности, должна
будет лежать на искомом пути.
Теперь решим исходную задачу для графа, не содержащего циклов.
Рассмотрим топологическую сортировку данного графа (подробнее см. в книге Кор-
мена раздел "Топологическая сортировка"). Возьмём отмеченные вершины в том
порядке, в котором они входят в эту топологическую сортировку. Если искомый
путь существует, то самой первой вершиной в этом списке будет вершина старта,
самой последней — вершина финиша, а для каждой пары соседних вершин этого
списка будет существовать некоторый путь из более ранней вершины в следующую.
Если это не выполняется, значит, что либо из стартовой вершины нельзя добраться
до всех остальных, либо не из всех отмеченных вершин можно добраться до фини-
ша, либо для каких-то двух отмеченных вершин u и v не существует пути как из u
в v, так и из v в u (если бы были оба таких пути, вершины u и v объединились бы
в одну компоненту сильной связности, а если нет ни одного пути, то очевидно, что
эти две вершины одному пути принадлежать не могут).
Теперь найдём путь, в ориентированном графе без циклов, содержащий заданные
вершины в определённом порядке. Это можно сделать, например, так. Пусть v1, v2,
. . ., vk — список обязательных вершин в порядке обхода. Найдём путь из v2 в v1
по обратным рёбрам, затем путь из v3 в v2 по обратным рёбрам, и т.д. до пути из