Cod sursa(job #575176)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 7 aprilie 2011 23:48:05
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <list>
#include <stack>

using namespace std;

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

const int N = 100010;

vector <int> rez;

list <int> L[N];

stack <int> s;

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() & 1)
            return false;
    return true;
}

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

void euler(int nc) {
    int newn;
    while (1) {
        if (L[nc].empty())
            break;
        newn = L[nc].back();
        s.push(nc);
        sterge(nc, newn);
        nc = newn;
    }
}

void ciclu_euler() {
    int v = 1;
    do {
        rez.push_back(v);
        euler(v);
        v = s.top();
        s.pop();
    }
    while (!s.empty());
}

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

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