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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Версия для печати больше не поддерживается и может содержать ошибки обработки. Обновите закладки браузера и используйте вместо этого функцию печати браузера по умолчанию.

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

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;
}

Ссылки