Pagini recente » Cod sursa (job #659258) | Cod sursa (job #435889) | Cod sursa (job #1499305) | Cod sursa (job #565306) | Cod sursa (job #1242781)
# include <bits/stdc++.h>
#define p(x) int(S[x].size())
using namespace std;
ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");
const int nmax = 100010;
stack < int > s;
vector < int > S[nmax];
int Sol[nmax],n;
bool b[nmax];
queue < int > q;
bool bfs()
{
q.push(1);b[1]=1;
while (q.size())
{
int v=q.back();q.pop();
for (int i=0,j=p(v);i<j;++i) if (!b[S[v][i]]) q.push(S[v][i]),b[S[v][i]]=1;
}
for (int i=1;i<=n;++i) if (!b[i]) return 0;
return 1;
}
bool eulerian()
{
for (int i=1;i<=n;++i) if (p(i) & 1) return 0;
return bfs();
}
int main(void)
{
int m;
fi>>n>>m;
int x,y;
while (m--) fi>>x>>y,S[x].push_back(y),S[y].push_back(x);
if (!eulerian()) return fo<<"-1\n",0;
s.push(1);
while (s.size())
{
int v=s.top();
if (!p(v)) Sol[++Sol[0]]=v,s.pop();
else
{
int to=S[v][p(v)-1];
s.push(to);
S[v].pop_back();
S[to].erase(find(S[to].begin(),S[to].end(),v));
}
}
for (int i=1;i<Sol[0];++i) fo << Sol[i] << ' ';
return 0;
}