Cod sursa(job #1444495)

Utilizator SmarandaMaria Pandele Smaranda Data 29 mai 2015 20:24:01
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <vector>

using namespace std;

const int N = 100002;

int grad [N];

pair <int, int> E [5 * N];
bool used [5 * N];
vector <int> graph [N], ans;

void euler (int x) {
    int fiu;
    vector <int> :: iterator it;

    for (it = graph [x].begin (); it != graph [x].end (); ++ it) {
        if (used [*it])
            continue;
        if (E [*it].first == x)
            fiu = E [*it].second;
        else fiu = E [*it].first;
        used [*it] = 1;
        euler (fiu);
    }
    ans.push_back (x);
}

int main () {
    int n, m, i, x, y;
    vector <int> :: iterator it;

    freopen ("ciclueuler.in", "r", stdin);
    freopen ("ciclueuler.out", "w", stdout);

    scanf ("%d%d", &n, &m);
    for (i = 1; i <= m; i ++) {
        scanf ("%d%d", &x, &y);
        grad [x] ++;
        grad [y] ++;
        E [i] = make_pair (x, y);
        graph [x].push_back (i);
        graph [y].push_back (i);
    }
    for (i = 1; i <= n; i ++)
        if (grad [i] % 2) {
            printf ("-1\n");
            return 0;
        }
    euler (1);
    for (it = ans.begin (); it != ans.end (); ++ it)
        printf ("%d ", *it);
    printf ("\n");
    return 0;
}