Pagini recente » Cod sursa (job #541161) | Cod sursa (job #2896390) | Cod sursa (job #377342) | Cod sursa (job #1223497) | Cod sursa (job #716336)
Cod sursa(job #716336)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define nMax 100010
using namespace std;
int n;
vector <int> graf[nMax];
vector <int> afis;
int grad[nMax];
int viz[nMax];
stack <int> stiva;
void citire()
{
int m;
scanf ("%d %d", &n, &m);
while (m --){
int x;
int y;
scanf ("%d %d", &x, &y);
graf[x].push_back (y);
graf[y].push_back (x);
grad[x] ++;
grad[y] ++;
}
}
void DFS(int nod)
{
for (unsigned int i = 0; i < graf[nod].size(); ++ i){
if (viz[graf[nod][i]] == 0){
viz[graf[nod][i]] = 1;
DFS(graf[nod][i]);
}
}
}
void verificareGrafEulerian()
{
DFS(1);
for (int i = 1; i <= n; ++ i){
if (viz[i] == 0){
printf ("-1\n");
exit(0);
}
if (grad[i] %2 != 0){
printf ("-1\n");
exit(0);
}
}
}
void sterge(int unde, int ce)
{
for (unsigned int i = 0; i < graf[unde].size(); ++ i){
if (graf[unde][i] == ce){
graf[unde].erase(graf[unde].begin() + i);
return;
}
}
}
void rez(int v)
{
while (!graf[v].empty()){
int x = graf[v].back();
graf[v].pop_back();
stiva.push(v);
sterge(x,v);
v = x;
}
}
void GrafEulerian()
{
int v = 1;
do{
rez(v);
v = stiva.top();
stiva.pop();
afis.push_back (v);
}while (!stiva.empty());
}
int main()
{
freopen ("ciclueuler.in", "r", stdin);
freopen ("ciclueuler.out", "w", stdout);
citire();
verificareGrafEulerian();
GrafEulerian();
for (int i = 0; i < afis.size(); ++ i){
printf ("%d ", afis[i]);
}
printf ("\n");
return 0;
}