Pagini recente » Cod sursa (job #2391487) | Cod sursa (job #1464732) | Cod sursa (job #1060083) | Cod sursa (job #891768) | Cod sursa (job #1219619)
#include<fstream>
#include<list>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define MAXN 100005
#define pb push_back
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
list <int> G[MAXN];
list <int>::iterator it;
vector <int> ciclu;
queue <int> q;
stack <int> S;
int N,M,deg[MAXN],viz[MAXN];
void read() {
int x,y,i;
cin>>N>>M;
for(i=1;i<=M;i++) {
cin>>x>>y;
G[x].pb(y); deg[x]++;
G[y].pb(x); deg[y]++; }
}
int eulerian() {
for(int i=1;i<=N;i++)
if (deg[i]%2 ) return 0;
return 1;
}
void sterge(int v,int w) {
deg[v]--; deg[w]--;
G[v].pop_front();
for(it=G[w].begin();it!=G[w].end();it++)
if(*it==v) {
G[w].erase(it);
break; }
}
void euler(int v) {
while( true ) {
if( G[v].empty() )
break;
int w = G[v].front();
S.push(v);
sterge(v,w);
v=w;
}
}
void iterativ(int v) {
do {
euler(v);
v=S.top(); S.pop();
ciclu.pb(v);
} while(!S.empty());
}
int main() {
int i;
read();
if (eulerian()) {
iterativ(1);
for(i=ciclu.size()-1;i>=0;i--)
cout<<ciclu[i]<<" "; }
else cout<<"-1";
return 0;
}