Cod sursa(job #656339)

Utilizator SpiderManSimoiu Robert SpiderMan Data 4 ianuarie 2012 14:46:54
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
# include <cstdio>
# include <stack>
# include <vector>
using namespace std;

const char *FIN = "ciclueuler.in", *FOU = "ciclueuler.out";
const int MAX_N = 100005;

vector <int> G[MAX_N], sol;
stack <int> stk;
int N, M;

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    scanf ("%d %d", &N, &M);
    for (int i = 1, x, y; i <= M; ++i) {
        scanf ("%d %d", &x, &y);
        G[x].push_back (y);
        G[y].push_back (x);
    }
    for (int i = 1; i <= N; ++i) {
        if (G[i].size () & 1) {
            printf ("-1");
            return 0;
        }
    }

    for (stk.push (1); !stk.empty (); ) {
        int x = stk.top ();
        if (G[x].size () == 0) {
            sol.push_back (x), stk.pop ();
            continue;
        }
        int y = G[x].back ();
        G[x].pop_back (), stk.push (y);
        for (vector <int> :: iterator it = G[y].begin (); it != G[y].end (); ++it) {
            if (*it == x) {
                G[y].erase (it);
                break ;
            }
        }
    }
    for (vector <int> :: iterator it = sol.end () - 1; it != sol.begin (); --it) {
        printf ("%d ", *it);
    }
}