Pagini recente » Cod sursa (job #3133578) | Cod sursa (job #429075) | Cod sursa (job #890865) | Cod sursa (job #1300855) | Cod sursa (job #2290398)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
pair <int,int> v[500001];
int cnt;
int e[500001];
bool marcat[500001],viz[500001];
vector <int> a[100001];
void dfs(int x)
{
int muchie,y;
viz[x]=1;
for(int i=0; i<a[x].size(); i++)
{
muchie=a[x][i];
y=v[muchie].second;
if(x==y)
y=v[muchie].first;
if(!viz[y])
dfs(y);
}
}
void euler(int x)
{
int muchie,y;
for(int i=0; i<a[x].size(); i++)
{
muchie=a[x][i];
if(!marcat[muchie])
{
marcat[muchie]=1;
y=v[muchie].second;
if(y==x)
y=v[muchie].first;
euler(y);
}
}
e[++cnt]=x;
}
int main()
{
int n,m,i,x,y;
in>>n>>m;
for(i=1; i<=m; i++)
{
in>>x>>y;
v[i].first=x;
v[i].second=y;
a[x].push_back(i);
a[y].push_back(i);
}
dfs(1);
for(i=1; i<=n; i++)
if(!viz[i])
{
out<<"-1";
return 0;
}
for(i=1; i<=n; i++)
if(a[i].size()%2)
cnt++;
if(cnt==0)
{
euler(1);
for(i=1; i<=cnt-1; i++)
out<<e[i]<<" ";
}
else
out<<"-1";
return 0;
}