Pagini recente » Cod sursa (job #3187422) | Cod sursa (job #1537309) | Cod sursa (job #3278203) | Cod sursa (job #2345312) | Cod sursa (job #1966597)
/*----Eulerian Cycle/Path
Eulerian Path is a path in graph that visits every edge exactly once.
cond : graph is connected + exacly 2 nodes with odd degree
Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.
cond : graph is connected + all nodes have even degree
*/
#include <bits/stdc++.h>
#define maxN 100002
FILE *fin = freopen("ciclueuler.in", "r", stdin);
FILE *fout = freopen("ciclueuler.out", "w", stdout);
using namespace std;
int N, M;
int gr[maxN];
vector <int> euler;
vector <int> G[maxN];
bitset <maxN> color;
void eulerianGraph(){
for(int i = 1; i <= N; ++ i)
if(gr[i] & 1){
printf("-1\n");
exit(0);
}
}
void erase_edge(int u, int v){
for(int i = 0; i < G[u].size(); ++ i)
if(G[u][i] == v)
G[u].erase(G[u].begin() + i);
}
void dfs(int node){
while(G[node].size()){
int son = G[node][0];
G[node].erase(G[node].begin());
erase_edge(son, node);
if(!color.test(son))
dfs(son);
}
color.set(node);
euler.push_back(node);
}
int main(){
scanf("%d %d", &N, &M);
for(int i = 1; i <= M; ++ i){
int x, y;
scanf("%d %d", &x, &y);
++ gr[x], ++ gr[y];
G[x].push_back(y);
G[y].push_back(x);
}
eulerianGraph();
dfs(1);
for(int node : euler)
printf("%d ", node);
return 0;
}