Недавно возник вопрос про реализацию поиска в глубину без рекурсии. Я умею просто обходить граф и помечать вершины из одной компоненты используя O(V) памяти на стек. При использовании рекурсии легко сделать пометки tin, tout(время входа и время выхода из вершины). А используя стек мне нужно O(V+E) памяти. Вопрос в том, чтобы использовать O(v) памяти на стек и получить пометки tin, tout.