Pagini recente » Cod sursa (job #385717) | Cod sursa (job #2594860) | Cod sursa (job #3210660) | Cod sursa (job #3212325) | Cod sursa (job #1316549)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
vector <int> v[100005];
queue <int> q;
int n,m,nod=1,gr[100005],st[500005],k,sol[500005],nsol,use[100005],ok=1;
void Del(int x,int y)
{ int i,j;
for(i=0;i<v[x].size();i++)
if (v[x][i]==y)
{ v[x][i]=v[x][v[x].size()-1];
v[x].pop_back();
break;
}
}
void BFS()
{ int i,x=1;
q.push(1);
use[1]=1;
while(!q.empty())
{
x=q.front(); q.pop();
for(i=0;i<v[x].size();i++)
if (!use[v[x][i]])
{q.push(v[x][i]); use[v[x][i]]=1;}
}
for(i=1;i<=n;i++)
if (!use[i]) ok=0;
}
void Euler(int x)
{ int i,y;
while(v[x].size())
{
y=v[x][0]; k++; st[k]=y;
Del(x,y);
Del(y,x);
x=y;
}
}
int main()
{ int i,j,x,y;
f>>n>>m;
for(i=1;i<=m;i++)
{ f>>x>>y;
gr[x]++; gr[y]++;
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1;i<=n;i++)
if (gr[i]%2!=0) ok=0;
BFS();
if (!ok) g<<"-1\n";
else
{ k=1; st[k]=1;
while(k)
{
Euler(st[k]);
nsol++; sol[nsol]=st[k]; k--;
}
}
for(i=1;i<nsol;i++)
g<<sol[i]<<" ";
return 0;
}