Pagini recente » Cod sursa (job #1774282) | Cod sursa (job #387760) | Cod sursa (job #1968784) | Cod sursa (job #2837254) | Cod sursa (job #591871)
Cod sursa(job #591871)
#include <cstdio>
#include <vector>
#include <stack>
#include <list>
using namespace std;
vector <int> g[100001];
stack <int> s;
list <int> l;
int n,m,vis[100001];
bool odd_degree()
{
int i;
for (i=1;i<=n;++i)
if (g[i].size()%2)
return 1;
return 0;
}
void dfs(int x)
{
unsigned int i;
for (i=0;i<g[x].size();++i)
if (!vis[g[x][i]])
{
vis[g[x][i]]=1;
dfs(g[x][i]);
}
}
bool unconnected()
{
int i;
dfs(1);
for (i=1;i<=n;++i)
if (!vis[i])
return 1;
return 0;
}
void cycle(int x)
{
int y;
unsigned int i;
while (g[x].size())
{
y=g[x][g[x].size()-1];
s.push(x);
g[x].pop_back();
for (i=0;i<g[y].size();++i)
if (g[y][i]==x)
break;
g[y][i]=g[y][g[y].size()-1];
g[y].pop_back();
x=y;
}
}
int main()
{
int i,x,y;
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d %d\n",&n,&m);
for (i=1;i<=m;++i)
{
scanf("%d %d\n",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
if (odd_degree()||unconnected())
{
printf("-1\n");
return 0;
}
do
{
cycle(x);
x=s.top();
s.pop();
l.push_back(x);
}
while (!s.empty());
for (;!l.empty();l.pop_front())
printf("%d ",l.front());
printf("\n");
return 0;
}