Pagini recente » Cod sursa (job #974017) | Cod sursa (job #2957813) | Cod sursa (job #3209755) | Cod sursa (job #1089471) | Cod sursa (job #665342)
Cod sursa(job #665342)
#include<cstdio>
#include<stack>
#include<list>
using namespace std;
int n,m,i,deg[100010],vis[100010],eulerian();
list<int> G[100010],SOL;
stack<int> Stack;
void read(),solve(),del(int,int),dfs(int,int&),cicle(int);
int main()
{
read();
solve();
return 0;
}
void read()
{
int x,y;
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
deg[x]++;deg[y]++;
}
}
void solve()
{
int v=eulerian();
if(!v)
printf("-1\n");
else
do{
cicle(v);
v=Stack.top();Stack.pop();
SOL.push_back(v);
}while(!Stack.empty());
for(list<int>::iterator it=SOL.begin();it!=SOL.end();it++)printf("%d ",*it);
}
int eulerian()
{
int k=0;dfs(1,k);
if(k!=n)return 0;
for(int i=1;i<=n;i++)if(deg[i]%2)return 0;
return 1;
}
void dfs(int node,int &k)
{
vis[node]=1;k++;
for(list<int>::iterator it=G[node].begin();it!=G[node].end();it++)
{
if(!vis[*it])
dfs(*it,k);
}
}
void cicle(int node)
{
while(!G[node].empty())
{
Stack.push(node);
int next=G[node].front();
del(node,next);
node=next;
}
}
void del(int u,int v)
{
deg[u]--;deg[v]--;
G[u].pop_front();
for(list<int>::iterator it=G[v].begin();it!=G[v].end();it++)
{
if(*it==u)
{
G[v].erase(it);break;
}
}
}