Pagini recente » Cod sursa (job #2950566) | Cod sursa (job #2185575) | Cod sursa (job #3244752) | Cod sursa (job #665059) | Cod sursa (job #1256335)
#include <cstdio>
#include <vector>
#include <set>
#include <stack>
#include <queue>
using namespace std;
#define NMAX 100007
vector < int > G[NMAX];
vector < int > sol;
queue < int > Q;
stack < int > S;
bool marked[NMAX];
int N,M,X,node,i,Y,current;
bool flag;
bool conex()
{
Q.push(1);
marked[1]=true;
bool flag=true;
int node,i;
while (!Q.empty())
{
node=Q.front();
for (vector < int > :: iterator u=G[node].begin();u!=G[node].end();++u)
{
if (marked[*u]) continue;
marked[*u]=true;
Q.push(*u);
}
Q.pop();
}
for (i=1;i<=N;++i) flag&=marked[i];
return flag;
}
void df(int node)
{
int e=node;
while (!G[e].empty())
{
S.push(e);
current=G[e][G[e].size()-1];
G[e].pop_back();
for (vector < int > :: iterator u=G[current].begin();u!=G[current].end();++u)
if (*u==e)
{
G[current].erase(u);
break;
}
e=current;
}
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
for (scanf("%d%d",&N,&M);M;--M)
{
scanf("%d%d",&X,&Y);
G[X].push_back(Y);
G[Y].push_back(X);
}
for (i=1;i<=N;++i)
if (G[i].size()&1 || !conex())
{
printf("-1\n");
return 0;
}
node=1;
while (!flag)
{
df(node);
node=S.top();
S.pop();
sol.push_back(node);
if (S.empty()) flag=true;
}
for (vector < int > :: iterator u=sol.begin();u!=sol.end();++u)
printf("%d ",*u);
return 0;
}