Pagini recente » Cod sursa (job #1901367) | Cod sursa (job #846190) | Cod sursa (job #1257505) | Cod sursa (job #2183462) | Cod sursa (job #1046267)
#include <fstream>
#include <vector>
#include <stack>
#define NMax 100002
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
vector <int> G[NMax];
int N,M,Grad[NMax],Use[NMax],Ok=1;
vector <int> Sol;
stack <int> S;
void Read()
{
fin>>N>>M;
for(int i=1;i<=M;i++)
{
int x,y;
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
Grad[x]++;Grad[y]++;
}
}
void DFS(int Nod)
{
Use[Nod]=1;
for(unsigned int i=0;i<G[Nod].size();i++)
{
if(!Use[G[Nod][i]])
DFS(G[Nod][i]);
}
}
void Cycle(int Nod)
{
while(G[Nod].size())
{
int Vecin=G[Nod][0];
S.push(Vecin);
G[Nod].erase(G[Nod].begin());
for(vector <int> :: iterator it=G[Vecin].begin();it!=G[Vecin].end();it++)
if(*it==Nod)
{
G[Vecin].erase(it);
break;
}
Nod=Vecin;
}
}
void Solve()
{
DFS(1);
for(int i=1;i<=N;i++)
{
if(Grad[i]%2 || !Use[i])
{
Ok=0;
return;
}
}
int Nod=1;
do
{
Cycle(Nod);
Nod=S.top();S.pop();
Sol.push_back(Nod);
}while(!S.empty());
}
void Print()
{
if(!Ok)
{
fout<<"-1\n";
return;
}
for(int i=0;i<Sol.size();i++)
fout<<Sol[i]<<" ";
fout<<"\n";
}
int main()
{
Read();
Solve();
Print();
return 0;
}