Циклы в графах

Эм, там в статье несколько опущен случай неориентированного графа (добавил себе в TODO).

Вообще для неор графа надо немножко изменить алгоритм: навесить одну доп. проверку. А именно, в функцию dfs передавать вершину p - это номер вершины, по которой мы попали в v. Тогда внутри dfs в цикле перед всеми остальными проверками надо дописать проверку:

if (to == p)  continue;

Тем самым мы избежим этой проблемы, которую вы описали: мы никогда не будем пытаться пройти по только что пройденному ребру в обратную сторону.

Соответственно, при вызове dfs (to) мы теперь ещё передаём вершину p, т.е. вместо этого пишем dfs (to, v). В основной программе вызывать надо dfs (i, -1).