Cod sursa(job #575165)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 7 aprilie 2011 23:21:51
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#define mp make_pair

using namespace std;

ifstream in ("ciclueuler.in");
ofstream out ("ciclueuler.out");

const int N = 100010;

vector <int> v, rez;

vector <pair <int, int> > L[N];

int n, gr[N];

bool used[5 * N];

void read() {
    int m, x, y;

    in >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        in >> x >> y;
        L[x].push_back(mp(y,i));
        L[y].push_back(mp(x,i));
    }
}

bool verif() {
    for (int i = 1; i <= n; ++ i)
        if (L[i].size() % 2 == 1)
            return false;
    return true;
}

void ciclu_euler() {
    int nc;
    bool ok;

    v.push_back(1);

    while (! v.empty()) {
        ok = false;
        nc = *(-- v.end());

        for (vector <pair <int, int> > :: iterator it = L[nc].begin(); it != L[nc].end(); ++ it)
            if (! used[it -> second]) {
                used[it -> second] = 1;
                v.push_back(it -> first);
                ok = true;
                break;
            }

        if (ok == false) {
            rez.push_back(nc);
            v.pop_back();
        }
    }
}

void afis() {
    vector <int> :: iterator it = rez.end();
    -- it;
    for (it = it; it != rez.begin(); -- it)
        out << *it << ' ';
}

int main() {
    read();
    if (! verif()) {
        out << "-1\n";
        return 0;
    }
    ciclu_euler();
    afis();
    return 0;
}