Pagini recente » Cod sursa (job #1517762) | Cod sursa (job #2842335) | Cod sursa (job #1295834) | Cod sursa (job #1744675) | Cod sursa (job #1329431)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define Nmax 100002
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
vector <int> G[Nmax],sol;
stack <int> S;
int n,use[Nmax];
void read()
{int m;
fin>>n>>m;
int i;
for(i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void Erase(int nod1, int nod2)
{
G[nod1].erase(G[nod1].begin());
for(unsigned int i=0;i<G[nod2].size();i++)
if(G[nod2][i]==nod1)
{
G[nod2].erase(G[nod2].begin()+i);
break;
}
}
void cycle(int nod)
{
while(G[nod].size())
{
S.push(nod);
int vecin=G[nod][0];
Erase(nod,vecin);
nod = vecin;
}
}
void solve()
{
int nod=1;
do
{
cycle(nod);
nod=S.top();
S.pop();
sol.push_back(nod);
}
while(!S.empty());
}
void DFS(int x)
{
use[x]=1;
for(unsigned int i=0;i<G[x].size();i++)
if(!use[G[x][i]])
DFS(G[x][i]);
}
int verif_euler()
{
DFS(1);
for(int i=1;i<=n;i++)
{
if(use[i]==0) return 0;
if(G[i].size()%2!=0) return 0;
}
return 1;
}
int main()
{
read();
if(verif_euler()==0) fout<<"-1";
else
{
solve();
for(unsigned int i=0;i<sol.size();i++)
fout<<sol[i]<<" ";
}
return 0;
}