Pagini recente » Cod sursa (job #6946) | Cod sursa (job #1843546) | Cod sursa (job #2175532) | Cod sursa (job #1710233) | Cod sursa (job #1133797)
#include<fstream>
#include<vector>
#include<queue>
#define pb push_back
using namespace std;
vector <int> gr[100001];
bool viz[100001];
queue <int> qvf;
vector <int> ciclu;
void bfs(int vf)
{
int i;
viz[vf]=1;
qvf.push(vf);
while(!qvf.empty())
{
vf=qvf.front();
qvf.pop();
for(i=0;i<gr[vf].size();i++)
if(!viz[gr[vf][i]])
{
qvf.push(gr[vf][i]);
viz[gr[vf][i]]=1;
}
}
}
bool eulerian(int n)
{
int i;
bfs(1);
for(i=1;i<=n;i++)
if((!viz[i]) || (gr[i].size()%2==1))
return 0;
return 1;
}
void sterge(int vf, int vf2)
{
vector <int>:: iterator it;
gr[vf].pop_back();
for(it=gr[vf2].begin();it!=gr[vf2].end();it++)
if(*it==vf)
{
gr[vf2].erase(it);
break;
}
}
void euler(int vf)
{
int vf2;
while(gr[vf].size())
{
vf2=gr[vf].back();
sterge(vf,vf2);
ciclu.pb(vf);
vf=vf2;
}
}
int main()
{
int n,m;
int i,j;
int xx,yy;
ifstream f("ciclueuler.in");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>xx>>yy;
gr[xx].pb(yy);
gr[yy].pb(xx);
}
f.close();
ofstream g("ciclueuler.out");
if(eulerian(n))
{
euler(1);
for(i=0;i<ciclu.size();i++)
g<<ciclu[i]<<" ";
g<<'\n';
}
else
g<<"-1\n";
g.close();
return 0;
}