Pagini recente » Cod sursa (job #829235) | Cod sursa (job #2473293) | Cod sursa (job #2351938) | Cod sursa (job #771477) | Cod sursa (job #1111447)
#include <cstdio>
#include <list>
#include <stack>
#define NMAX 100001
using namespace std;
int n,m,k;
int Sol[NMAX];
bool vizitat[NMAX];
int degree[NMAX];
list < int > Graf[NMAX];
stack < int > S;
void read(){
int x,y;
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
Graf[x].push_back(y);
Graf[y].push_back(x);
++degree[x];
++degree[y];
}
}
void DFS(int node){
vizitat[node] = 1;
for(list < int > ::iterator it = Graf[node].begin(); it!=Graf[node].end();++it)
if(!vizitat[*it])
DFS(*it);
}
bool este_eulerian(){
DFS(1);
for(register int i=1;i<=n;++i)
if(!vizitat[i])
return 0;
for(register int i=1;i<=n;++i)
if(degree[i]%2 != 0)
return 0;
return 1;
}
void sterg(int v,int w){
--degree[v];
--degree[w];
Graf[v].pop_front();
for(list < int > ::iterator it = Graf[w].begin(); it!= Graf[w].end(); ++it)
if(*it == v){
Graf[w].erase(it);
break;
}
}
void euler(int node){
while(!Graf[node].empty()){
int w = Graf[node].front();
S.push(node);
sterg(node,w);
node = w;
}
}
void solve(){
int node = 1;
do{
euler(node);
node = S.top();
S.pop();
Sol[++k] = node;
}while(!S.empty());
}
void write(){
if(!este_eulerian())
printf("-1");
else{
solve();
for(register int i=k;i>0;--i)
printf("%d ",Sol[i]);
}
}
int main(){
read();
write();
return 0;
}