Pagini recente » Cod sursa (job #876450) | Cod sursa (job #1751651) | Cod sursa (job #2528390) | Cod sursa (job #141125) | Cod sursa (job #1111121)
#include <cstdio>
#include <list>
#include <stack>
#define Nmax 100005
using namespace std;
int N, M, D[Nmax], Viz[Nmax];
list <int> G[Nmax], L;
stack <int> St;
void Citire()
{
int x, y;
scanf("%d %d", &N, &M);
for (int i = 1; i <= M; ++i)
{
scanf("%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
D[x]++;
D[y]++;
}
}
void DFS(int nod)
{
list <int> :: iterator it;
Viz[nod] = 1;
Viz[0]++;
for (it = G[nod].begin(); it != G[nod].end(); ++it)
if (!Viz[*it])
DFS(*it);
}
int Eulerian()
{
for (int i = 1; i <= N; ++i)
if (!Viz[i])
DFS(i);
if (Viz[0] != N)
return 0;
for (int i = 1; i <= N; ++i)
if (D[i] % 2)
return 0;
return 1;
}
void Stergere(int x, int y)
{
list <int> :: iterator it;
D[x]--;
D[y]--;
G[x].pop_front();
for (it = G[y].begin(); it != G[y].end(); ++it)
if (x == *it)
{
G[y].erase(it);
break;
}
}
void Ciclu(int x)
{
int y;
while (!G[x].empty())
{
y = G[x].front();
St.push(x);
Stergere(x, y);
x = y;
}
}
void Rezolvare()
{
int x = 1;
if (!Eulerian())
{
printf("-1");
return;
}
do
{
Ciclu(x);
x = St.top();
St.pop();
L.push_back(x);
}while (!St.empty());
}
void Afisare()
{
int a;
while (!L.empty())
{
a = L.front();
L.pop_front();
printf("%d ", a);
}
}
int main()
{
freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
Citire();
Rezolvare();
Afisare();
return 0;
}