Pagini recente » Cod sursa (job #657871) | Cod sursa (job #1596366) | Cod sursa (job #2137831) | Cod sursa (job #1617871) | Cod sursa (job #1075858)
#include <fstream>
#include <list>
#include <stack>
#define NMax 100005
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
list <int> G[NMax],Sol;
stack <int> S;
int N,M,Deg[NMax],Solution;
bool Use[NMax];
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);
Deg[x]++;Deg[y]++;
}
}
void DFS(int Nod)
{
Use[Nod]=1;
for(list<int> :: iterator it=G[Nod].begin();it!=G[Nod].end();it++)
{
int Vecin=*it;
if(!Use[Vecin])
DFS(Vecin);
}
}
int Check()
{
DFS(1);
for(int i=1;i<=N;i++)
if(Use[i]==0)
return 0;
for(int i=1;i<=N;i++)
if(Deg[i]%2==1)
return 0;
return 1;
}
void Erase(int x, int y)
{
G[x].pop_front();
for(list<int> :: iterator it=G[y].begin();it!=G[y].end();it++)
{
if(*it==x)
{
G[y].erase(it);
break;
}
}
}
void Euler(int x)
{
while(!G[x].empty())
{
int y=G[x].front();
S.push(x);Erase(x,y);
x=y;
}
}
void Solve()
{
if(Check()==0)
{
Solution=-1;
return;
}
int x=1;
do
{
Euler(x);
x=S.top(); S.pop();
Sol.push_back(x);
}
while(!S.empty());
}
void Print()
{
if(Solution==-1)
{
fout<<"-1\n";
}
else
{
for(list<int> :: iterator it=Sol.begin();it!=Sol.end();it++)
fout<<*it<<" ";
fout<<"\n";
}
}
int main()
{
Read();
Solve();
Print();
return 0;
}