Как найти рекурсивным способом эйлеров путь в графе, из какой вершины начинать?

Question

[dalbio]

Мне нужно найти эйлеров путь в ориентированном графе, в интернете я нашёл статью в статье сказано:

После ввода графа нужно запустить euler(0) или от любой другой вершины.

,но это не работает для ориентированного графа, тогда как мне быть?
Заранее спасибо за ответ.

Answer 1

[Wataru]

Эйлеров цикл существует в графе, только если входная степень каждой вершины равна ее выходной степени.

Эйлеров путь существует от вершины с выходной степенью на 1 больше входной степени до вершины у которой входная степень на 1 больше, чем выходная. (Если граф неориентированный, то путь от одной нечетной вершины до другой). При этом все остальные вершины должны быть сбалансированны.

Это элементарно доказать - путь в каждую вершину входит сколько-то раз и столько же раз выходит. Исключение - только начальная и конечная вершина, если они не совпадают.

Соответственно, вам надо подсчитать степени всех вершин, проверить что все хорошо (максимум одна с in==out+1 и одна с in==out-1) и запустить или от любой или от той, у которой исходящих ребер больше.