Pagini recente » Cod sursa (job #2284239) | Cod sursa (job #311091) | Cod sursa (job #2300564) | Autentificare | Cod sursa (job #394491)
Cod sursa(job #394491)
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<list>
using namespace std;
#define foreach(v) for(typeof (v).begin() it=(v).begin();it!=(v).end();it++)
queue<int> q;
vector<int> G[100010];
vector<int> La;
int viz[100010]={0};
vector<int> stack;
int n,m;
ofstream fout("ciclueuler.out");
void bfs()
{int u;
q.push(1);
viz[1]=1;
while(!q.empty())
{u=q.front();
q.pop();
foreach(G[u])
if(viz[*it]==0)
{ q.push(*it);
viz[*it]=1;
}
}
}
int verif()
{int i;
for( i=1;i<=n;i++)
if(G[i].size()%2!=0)
return 0;
bfs();
for(i=1;i<=n;i++)
if(viz[i]==0)
return 0;
return 1;
}
void sterge(int v,int w)
{G[v].erase(G[v].begin());
foreach(G[w])
{if(*it==v)
G[w].erase(it);
break;
}
}
void euler(int v)
{
while(!G[v].empty())
{int w=G[v].front();
stack.push_back(w);
sterge(v,w);
v=w;
}
}
void rez(int x)
{int v;
if(!x)
fout<<-1;
else
{v=1;
stack.push_back(v);
while(!stack.empty())
{v=stack.back();
euler(v);
stack.pop_back();
La.push_back(v);
}
foreach(La)
fout<<*it<<" ";
}
}
int main()
{int alfa,beta,i;
ifstream fin("ciclueuler.in");
fin>>n>>m;
for(i=1;i<=m;i++)
{fin>>alfa>>beta;
G[alfa].push_back(beta);
G[beta].push_back(alfa);
}
fin.close();
rez(verif());
fout.close();
return 0;
}