Cod sursa(job #1383116)

Utilizator mariusadamMarius Adam mariusadam Data 9 martie 2015 21:49:50
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#include <stack>
#define n_max 100002

using namespace std;

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

vector <int> G[n_max], sol;
stack <int> S;
int n,m;

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

void read() {
    int i,j,k;
    r>>n>>m;
    for (k=1; k<=m; k++) {
        r>>i>>j;
        G[i].push_back(j);
        G[j].push_back(i);
    }
}

void ciclu(int x) {
    int nod,y;
    S.push(x);
    while (!S.empty()) {
        nod=S.top();
        if (!G[nod].empty()) {
            y=G[nod].back();
            S.push(y);
            G[nod].pop_back();
            for (vector <int>::iterator it=G[y].begin();it!=G[y].end(); it++)
                if (*it==nod) {
                    G[y].erase(it);
                    break;
                }
        }
        else {
            S.pop();
            sol.push_back(nod);
        }
    }
}

int main() {
    read();
    if (eulerian()) {
        ciclu(1);
        for (vector <int>::iterator it=sol.begin(); it!=sol.end(); it++)
            w<<*it<<" ";
    }
    else
        w<<-1;
    r.close();
    w.close();
    return 0;
}