Pagini recente » Cod sursa (job #814167) | Cod sursa (job #2609811) | Cod sursa (job #135173) | Cod sursa (job #329420) | Cod sursa (job #1509267)
using namespace std;
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#define pb push_back
#define NX 100010
FILE *f=fopen ("ciclueuler.in","r");
FILE *g=fopen ("ciclueuler.out","w");
list<int>G[NX],L;
stack<int>S;
queue<int>Q;
int N,M,deg[NX],col[NX];
void cit()
{
int u,v;
fscanf(f,"%d%d",&N,&M);
while(M--)
{
fscanf(f,"%d%d",&u,&v);
G[u].pb(v);deg[u]++;
G[v].pb(u);deg[v]++;
}
}
void BFS(int v)
{
Q.push(v);col[v]=1;
while(!Q.empty())
{
v=Q.front(); Q.pop();
list<int>::iterator w;
for(w=G[v].begin(); w!=G[v].end(); w++)
if(col[*w]==0)
Q.push(*w), col[*w]=1;
}
}
int este_conex()
{
BFS(1);
for(int v=2;v<=N;v++)
if(col[v]==0)
return 0;
return 1;
}
int eulerian()
{
if(este_conex()==0)
return 0;
for(int v=1;v<=N;v++)
if(deg[v]%2==1)
return 0;
return 1;
}
void sterge(int v,int w)
{
deg[v]--;
deg[w]--;
G[v].pop_front();
list<int>::iterator it;
for(it=G[w].begin();it!=G[w].end();it++)
if(*it==v)
{
G[w].erase(it);
break;
}
}
void euler(int v)
{
while(true)
{
if(G[v].empty())
break;
int w=G[v].front();
S.push(v);
sterge(v,w);
v=w;
}
}
int rez()
{
int v=eulerian();
if(v==0)
return -1;
do
{
euler(v);
v=S.top();S.pop();
L.pb(v);
} while(!S.empty());
return 1;
}
void scr(int x)
{
if(x==-1)
fprintf(g,"-1");
else
{
list<int>::iterator v;
for(v=L.begin();v!=L.end();v++)
fprintf(g,"%d ",*v);
}
}
int main()
{
cit();
scr(rez());
return 0;
}