Pagini recente » Cod sursa (job #465808) | Cod sursa (job #2598400) | Cod sursa (job #998442) | Cod sursa (job #2768340) | Cod sursa (job #2770811)
#include <bits/stdc++.h>
using namespace std;
struct EulerWalk {
int n;
vector<vector<pair<int, int>>> graph;
vector<int> cap, walk, buf, deg;
EulerWalk(int n) : n(n), graph(n + 1), deg(n + 1) {}
int AddEdge(int a, int b, int c = 1) {
int ret = cap.size();
graph[b].emplace_back(a, ret);
graph[a].emplace_back(b, ret);
cap.push_back(c);
deg[a] += c; deg[b] += c;
return ret;
}
void dfs(int node) {
while (graph[node].size()) {
int vec, ei; tie(vec, ei) = graph[node].back();
if (!cap[ei]) graph[node].pop_back();
else --cap[ei], dfs(vec);
}
walk.push_back(node);
}
void Go(ostream& cout) {
for (int i = 0; i < n; ++i) {
if (deg[i] == 0 || deg[i] % 2) {
cout << -1 << '\n';
return;
}
}
dfs(0);
if (walk.size() <= cap.size()) {
cout << -1 << '\n';
} else {
walk.pop_back();
for (auto node : walk)
cout << node + 1 << " ";
cout << endl;
}
}
};
int main() {
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
int n, m; cin >> n >> m;
EulerWalk E(n);
for (int i = 0; i < m; ++i) {
int a, b; cin >> a >> b;
E.AddEdge(a - 1, b - 1);
}
E.Go(cout);
return 0;
}