Pagini recente » Cod sursa (job #767485) | Cod sursa (job #1501815) | Cod sursa (job #3120913) | Cod sursa (job #103128) | Cod sursa (job #1128038)
/*
Keep It Simple!
*/
#include<stdio.h>
#include<list>
#define MaxN 100008
using namespace std;
list<int> G[MaxN],Queue,E,S;
int n,m;
bool viz[MaxN];
void DFS(int node)
{
viz[node] = 1;
for(list<int>::iterator it = G[node].begin(); it!=G[node].end();it++)
if(!viz[*it])
DFS(*it);
}
int E_Euler()
{
for(int i=1;i<=n;i++)
if(G[i].size()%2)
return 0;
DFS(1);
for(int i=1;i<=n;i++)
if(viz[i] == 0)
return 0;
return 1;
}
int sw;
void DeleteRoad(int a,int b)
{
G[a].pop_front();
for(list<int>::iterator it = G[b].begin();it!=G[b].end();it++)
if( *it == a )
{
G[b].erase(it); break;
}
}
void Ciclu_Euler(int node)
{
do
{
while(G[node].size())
{
int aux = G[node].front();
DeleteRoad(node,aux);
S.push_back(node);
node = aux;
}
node = S.back();
S.pop_back();
E.push_front(node);
}while(S.size());
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
if(E_Euler())
{
Ciclu_Euler(1);
for(list<int>::iterator it=E.begin(); it!=E.end();it++)
printf("%d ",*it);
}
else
printf("-1");
}