Cod sursa(job #575179)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 7 aprilie 2011 23:59:39
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <vector>
#include <list>

using namespace std;

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

const int N = 100010;

vector <int> v, rez;

list <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(y);
        L[y].push_back(x);
    }
}

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

void del(int a, int b) {
    L[a].pop_front();
    for (list <int> :: iterator it = L[b].begin() ; it != L[b].end(); ++ it)
        if(*it == a) {
            L[b].erase(it);
            break;
        }
}

void ciclu_euler() {
    int nc;

    v.push_back(1);

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

        if (L[nc].empty()) {
            rez.push_back(nc);
            v.pop_back();
            continue;
        }

        v.push_back(L[nc].front());
        del(nc, L[nc].front());
    }
}

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;
}