Pagini recente » Cod sursa (job #124471) | Profil IacobTudor | Cod sursa (job #105469) | Cod sursa (job #153181) | Cod sursa (job #1219596)
#include<fstream>
#include<list>
#include<algorithm>
#include<vector>
#include<queue>
#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;
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]++; }
}
void BFS() {
int x,i;
q.push(1);
while(!q.empty()) {
x=q.front();
q.pop();
viz[x]=1;
for(it=G[x].begin();it!=G[x].end();it++)
if(!viz[*it])
q.push(*it);
}
}
int eulerian() {
BFS();
for(int i=1;i<=N;i++)
if (!viz[i] || 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) {
int w;
while(G[v].size()) {
w=G[v].front();
sterge(v,w);
euler(w); }
ciclu.pb(v);
}
int main() {
int i;
read();
if (eulerian()) {
euler(1);
for(i=0;i<ciclu.size();i++)
cout<<ciclu[i]<<" "; }
else cout<<"-1";
return 0;
}