Эйлеров цикл. Эйлеров путь: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 8: Строка 8:
         eulerRec(graph, to, cycle);
         eulerRec(graph, to, cycle);
     }
     }
     cycle.push_front(v);
     cycle.push_back(v);
  }
  }
   
   

Текущая версия от 21:32, 19 июня 2021

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

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

Ссылки