Pagini recente » Cod sursa (job #815078) | Cod sursa (job #2327316) | Cod sursa (job #582225) | Cod sursa (job #968724) | Cod sursa (job #3245918)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
const int MMAX = 5e5;
vector<pair<int, int>> G[NMAX + 1];
int grad[NMAX + 1];
int visN[NMAX + 1], visM[MMAX + 1];
vector<int> sol;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
void dfs(int node) {
visN[node] = 1;
for(auto next : G[node]) {
if(!visN[next.first]) {
dfs(next.first);
}
}
}
void euler(int node) {
//back si pop_back au complexitate O(1)
while(G[node].size() > 0) {
int next = G[node].back().first;
int next_edge = G[node].back().second;
G[node].pop_back();
if(!visM[next_edge]) {
visM[next_edge] = 1;
euler(next);
}
}
sol.push_back(node);
}
int main() {
int n, m;
f >> n >> m;
for(int i = 1; i <= m; i++) {
int a, b;
f >> a >> b;
grad[a]++;
grad[b]++;
G[a].push_back({b, i});
G[b].push_back({a, i});
}
dfs(1);
int ok = 1;
for(int i = 1; i <= n; i++) {
if(visN[i] == 0 || grad[i] % 2 == 1) {
ok = 0;
}
}
if(ok == 0) {
g << -1;
} else {
euler(1);
sol.pop_back();
for(auto it : sol) {
g << it << ' ';
}
}
return 0;
}