Описание алгоритма
Euler tour tree - алгоритм, одновременно умеющий и обходить дерево, сводя его к массиву, длины , а также выводить эйлеров путь/цикл в графе за , где - кол-во ребер в графе.
Принцип работы
Суть алгоритма крайне проста, создадим глобальный массив, в который мы будем пихать вершинки по такому правилу, в DFS после запуска от потомка мы ждем, пока он не закончит свою работу, а потом добавляем в глобальный массив текущую вершину. В том случае, если мы ищем эйлеров путь, нам дополнительно нужно удалять все ребра, по которым мы прошли, или помечать их, чтобы все это дело не зациклилось. Утверждение. Этот алгоритм правильно находит эйлеров путь в графе. Доказательство. Запустим DFS от текущей вершинки. c