Существует ли путь через все вершины ориентированного графа?

Последнее предположение неверно. Например, взгляните на график G = (V,E), где E = {(v_i,v_j) | i < j } График явно является DAG. поэтому нахождение максимальной компоненты сильной связи не изменит граф. Кроме того, граф имеет гамильтонов путь, однако d_out(v_1) > 1 [при условии |V| > 3].

Однако - вы на правильном пути.

Алгоритм в псевдокоде высокого уровня:

1. найти максимальные сильно связанные компоненты в графе - результирующий граф является DAG.
2. Используйте топологическую сортировку полученного графа¹.
3. Проверьте, создает ли упорядоченная сортировка гамильтонов путь
4. если да - верни true, иначе верни false

Претензия:

Путь со всеми вершинами существует тогда и только тогда, когда DAG, представляющий MSCC графа, имеет гамильтонов путь.

Доказательство утверждения:
‹-
если есть гамильтонов путь - то такой путь тривиален, для каждого MSCC - путь проходит через все вершины , а затем к внешнему ребру, которое представляет наше ребро, выбранное на гамильтоновом пути в графе MSCC.
->
Если такой путь существует, пусть он будет v0->v1->...vm.
Обозначим через V_i максимальную сильно связную компоненту, в которой лежит v_i.
Теперь для пути в исходном графе v0->v1->...->vm есть также путь в графе MSCC²: V_0->V_1->...->V_m.
Обратите внимание, что если V_i появляется дважды [или более] в указанном выше пути - два вхождения являются смежными друг с другом, в противном случае найденный MSCC не будет максимальным, потому что если V_i->V_k->...->V_i допустимый путь - тогда V_i и V_k не максимальны, так как вы можете объединить их в один большой SCC.
Теперь для каждого V_i объедините все его вхождения в одно, и вы получите путь, где каждый V_i появляется не более одного раза [мы только что показали, почему], и ровно один [поскольку каждый v_i был на исходном пути и мы не удаляли полностью MSCC - просто свернули их].
Таким образом, сгенерированный путь является гамильтоновым путем в графе MSCC.

Доказательство правильности предложенного алгоритма:
Поскольку мы показали, что гамильтонов путь в графе MSCC существует тогда и только тогда, когда запрошенный путь существует в исходном графе, то:
- >
Алгоритм вернул true -> Алгоритм нашел гамильтонов путь в DAG -> В DAG есть гамильтонов путь [сноска 1] -> Имеется путь, как запрошено в оригинале график.
‹-
Алгоритм вернул false -> Алгоритм не нашел гамильтонов путь в DAG -> В DAG нет гамильтонова пути [сноска 1] -> В исходном пути нет запрошенного пути.

QED

1: в DAG есть уникальная топологическая сортировка, если существует гамильтонов путь, а если есть гамильтонов путь - это порядок вершин в топологической сортировке. Таким образом, в DAG найти гамильтонов путь несложно.
2: На самом деле, это небольшая модификация, V_i->V_i на самом деле не является ребром на графике MSCC, но пока давайте обозначим его как единицу.