Cod sursa(job #1002012)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 26 septembrie 2013 18:26:19
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <cstdio>
#include <list>
#include <vector>
#include <bitset>
#include <cstdlib>
using namespace std;

const int NMAX = 100003;

list <int> G[NMAX];
vector <int> S, R;
bitset <NMAX> viz;
int N;

inline bool is_connected () {

    int cnode, s = 0;
    list <int> :: iterator i;
    S.push_back (1);
    viz[1] = 1;
    while (!S.empty ()) {
        cnode = S.back ();
        S.pop_back ();
        ++s;
        for (i = G[cnode].begin (); i != G[cnode].end (); ++i)
            if (!viz[*i])
                viz[*i] = 1,
                S.push_back (*i);
    }
    if (s != N)
        return 0;
    return 1;

}

inline void delete_edge (const int &node, const int &_node) {

    for (list <int> :: iterator i = G[_node].begin (); i != G[_node].end (); ++i)
        if (*i == node) {
            G[_node].erase (i);
            return;
        }

}

inline void euler (int node) {

    int w;
    while (!G[node].empty ()) {
        w = G[node].front ();
        S.push_back (w);
        delete_edge (node, w);
        w = node;
        node = G[w].front ();
        G[w].pop_front ();
    }
    S.pop_back ();

}

inline void DFS () {

    int cnode;
    S.push_back (1);
    while (!S.empty ()) {
        cnode = S.back ();
        euler (cnode);
        R.push_back (S.back ());
    }

}

int main () {

    freopen ("ciclueuler.in", "r", stdin);
    freopen ("ciclueuler.out", "w", stdout);
    int M, i, a, b;
    scanf ("%d%d", &N, &M);
    for (i = 1; i <= M; ++i)
        scanf ("%d%d", &a, &b),
        G[a].push_back (b),
        G[b].push_back (a);
    for (i = 1; i <= N; ++i)
        if (G[i].size () & 1)
            printf ("-1"),
            exit (EXIT_SUCCESS);
    if (!is_connected ())
        printf ("-1"),
        exit (EXIT_SUCCESS);
    DFS ();
    for (i = 0; i < R.size () - 1; ++i)
        printf ("%d ", R[i]);

}