Эйлеров цикл. Эйлеров путь

Рекурсивная реализация

void eulerRec(vector<multiset<int>> &graph, int v, vector<int> &cycle) {
    while (!graph[v].empty()) {
        int to = *graph[v].begin();
        graph[v].erase(graph[v].find(to));
        //graph[to].erase(graph[to].find(v));
        eulerRec(graph, to, cycle);
    }
    cycle.push_back(v);
}

vector<int> euler(vector<multiset<int>> &graph) {
    vector<int> cycle;
    eulerRec(graph, 0, cycle);
    reverse(cycle.begin(), cycle.end());
    return cycle;
}

Итеративная реализация

vector<int> euler(vector<multiset<int>> &graph) {
    vector<int> stack = { 0 }, cycle;
    while (!stack.empty()) {
        int v = stack.back();
        if (!graph[v].empty()) {
            int to = *graph[v].begin();
            graph[v].erase(graph[v].find(to));
            //graph[to].erase(graph[to].find(v));
            stack.push_back(to);
        } else {
            stack.pop_back();
            cycle.push_back(v);
        }
    }
    reverse(cycle.begin(), cycle.end());
    return cycle;
}

Ссылки

• e-maxx — Нахождение Эйлерова пути
• neerc.ifmo.ru/wiki — Алгоритм построения Эйлерова цикла
• algorithmica.org — Эйлеров путь и цикл