Pagini recente » Cod sursa (job #1587288) | Cod sursa (job #1872776) | Cod sursa (job #1079564) | Cod sursa (job #518838) | Cod sursa (job #3226446)
#include <bits/stdc++.h>
#define Nmax 100005
#define Mmax 500005
using namespace std;
int st[Mmax],dr[Mmax],sol[Nmax],N;
bool viz[Mmax],vizz[Nmax];
vector <int> L[Nmax];
inline void Dfss(int nod)
{
vizz[nod]=true;
vector <int>:: iterator it;
for(it=L[nod].begin();it!=L[nod].end();++it)
if(!vizz[st[*it]+dr[*it]-nod])
Dfss(st[*it]+dr[*it]-nod);
}
inline bool Conex()
{
Dfss(1);
for(int i=1;i<=N;++i)
if(!vizz[i])
return false;
return true;
}
inline bool Este_Euler()
{
if(!Conex())
return false;
for(int i=1;i<=N;++i)
if(L[i].size()&1)
return false;
return true;
}
inline void Dfs(int nod)
{
vector <int>::iterator it;
for(it=L[nod].begin();it!=L[nod].end();++it)
if(!viz[*it])
{
viz[*it]=true;
Dfs(st[*it]+dr[*it]-nod);
}
sol[++sol[0]]=nod;
}
int main()
{
int M,i;
ifstream f ("ciclueuler.in");
ofstream g ("ciclueuler.out");
f >> N >> M;
for(i=1;i<=M;++i)
{
f >> st[i] >> dr[i];
L[st[i]].push_back(i);
L[dr[i]].push_back(i);
}
if(!Este_Euler())
printf("-1\n");
else
{
Dfs(1);
for(i=1;i<sol[0];++i)
g << sol[i] << " ";
}
return 0;
}