Pagini recente » Cod sursa (job #1286773) | Cod sursa (job #1745483) | Cod sursa (job #631019) | Cod sursa (job #3136836) | Cod sursa (job #2321929)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
const int NMax = 100000;
int N,M;
int Use[NMax + 5],Degree[NMax + 5];
vector <int> G[NMax+5],Sol;
stack <int> Stack;
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);
Degree[x]++;
Degree[y]++;
}
}
void DFS(int Nod)
{
Use[Nod] = 1;
for(int i = 0; i < (int)G[Nod].size(); ++i)
{
int Vecin = G[Nod][i];
if(!Use[Vecin])
DFS(Vecin);
}
}
void Delete(int X, int Y)
{
G[X].erase(G[X].begin());
for(int i = 0; i < (int)G[Y].size(); ++i)
if(G[Y][i] == X)
{
G[Y].erase(G[Y].begin() + i);
break;
}
}
void FindCycle(int Nod)
{
while(G[Nod].size())
{
int Vecin = G[Nod][0];
Stack.push(Nod);
Delete(Nod,Vecin);
Nod = Vecin;
}
}
void Euler()
{
int Nod = 1;
do
{
FindCycle(Nod);
int NewNode=Stack.top();
Stack.pop();
Sol.push_back(NewNode);
Nod = NewNode;
}while(!Stack.empty());
}
void Print()
{
for(int i = 0; i < (int)Sol.size(); ++i)
fout << Sol[i] << " ";
fout << "\n";
}
int main()
{
Read();
DFS(1);
int Ok = 1;
for(int i = 1; i <= N; ++i)
{
if (Use[i] == 0)
Ok = 0;
if(Degree[i]%2)
Ok = 0;
}
if(Ok)
{
Euler();
Print();
}
else
fout << "-1\n";
return 0;
}