Эйлеров цикл. Эйлеров путь
Перейти к навигации
Перейти к поиску
Рекурсивная реализация
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;
}