Pagini recente » Cod sursa (job #1628938) | Cod sursa (job #1143668) | Cod sursa (job #1893376) | Istoria paginii runda/oni.test-2010_runda3/clasament | Cod sursa (job #1971748)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#define maxn 100005
using namespace std;
int n,m,dg[maxn],viz[maxn];
vector <int > g[maxn],fin;
stack < int > st;
queue <int > q;
void citesc ()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
dg[x]++;
dg[y]++;
}
}
void bfs()
{
q.push(1);
while (!q.empty())
{
int nod=q.front();
q.pop();
for (vector <int > :: iterator it=g[nod].begin();it!=g[nod].end();++it)
if (!viz[*it])
{
viz[*it]=1;
q.push(*it);
}
}
}
bool e_conex()
{
bfs();
for (int i=1;i<=n;++i)
if (!viz[i])
return 0;
return 1;
}
bool euler()
{
if (!e_conex())
return 0;
for (int i=1;i<=n;++i)
if (dg[i]%2!=0)
return 0;
return 1;
}
void rez(int v)
{
while (1)
{
if (g[v].empty())
break;
int w=g[v].front();
st.push(v);
for (vector <int > :: iterator it=g[w].begin();it!=g[w].end();++it)
if (*it==v)
{
g[w].erase(it);
break;
}
g[v].erase(g[v].begin());
v=w;
}
}
void solv()
{
if (euler()==0)
{
printf("-1");
return;
}
int v=1;
do
{
rez(v);
v=st.top();
st.pop();
fin.push_back(v);
}
while (!st.empty());
for (vector <int > :: iterator it=fin.begin();it!=fin.end();++it)
printf("%d ",*it);
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
citesc();
solv();
return 0;
}