Pagini recente » Cod sursa (job #1185444) | Cod sursa (job #2001815) | Cod sursa (job #611528) | Cod sursa (job #992766) | Cod sursa (job #1216064)
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
using namespace std;
#define NMAX 100005
#define PB push_back
#define MP make_pair
#define PII pair < int , int >
int degree[NMAX];
bool sel[NMAX];
int node=1,M,N,X,Y;
list < int > G[NMAX];
list < int > :: iterator itV;
stack < int > S;
list < int > sol;
queue < int > Q;
bool condition()
{
queue < int > Q;
int node;
Q.push(1);
sel[1]=true;
while (!Q.empty())
{
node=Q.front();
Q.pop();
for (itV=G[node].begin();itV!=G[node].end();++itV)
{
if (sel[*itV]) continue;
sel[*itV]=true;
Q.push(*itV);
}
}
for (int i=1;i<=N;++i)
if (!sel[i] || (degree[i]&1))
return false;
return true;
}
void Delete(PII T)
{
--degree[T.first];
--degree[T.second];
list < int > :: iterator itV;
G[T.first].pop_front();
for (itV=G[T.second].begin();itV!=G[T.second].end();++itV)
if (*itV==T.first)
{
G[T.second].erase(itV);
return ;
}
}
void euler(int start)
{
int i,node=start;
while (!G[node].empty())
{
i=G[node].front();
S.push(node);
Delete(MP(node,i));
node=i;
}
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d%d",&N,&M);
while (M--)
{
scanf("%d%d",&X,&Y);
G[X].PB(Y);
++degree[X];
G[Y].PB(X);
++degree[Y];
}
if (!condition())
{
printf("-1\n");
return 0;
}
do
{
euler(node);
node=S.top();
S.pop();
sol.PB(node);
} while (!S.empty());
for (itV=sol.begin();itV!=sol.end();++itV)
printf("%d ",*itV);
return 0;
}