Cod sursa(job #1099592)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 5 februarie 2014 23:04:12
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<fstream>
#include <algorithm>
#include<vector>
#include<stack>
using namespace std;

stack <int> Stack;
vector <int> v[100010],Answer;
int n,m,grad[100010],ok;

void citire() {

    ifstream in("ciclueuler.in");
    int i,x,y;
    in>>n>>m;
    for(i=1;i<=m;i++) {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
        grad[x]++;
        grad[y]++;
    }
    in.close();

}

int validare_ciclu_eulerian() {

    int i;
    for(i=1;i<=n;i++)
        if(grad[i]%2==1)
            return 0;
    return 1;

}

void sterge_muchie(int nod,int vecin) {

    v[nod][0]=v[nod][v[nod].size()-1];
    v[nod].pop_back();
    v[vecin].erase(find(v[vecin].begin(),v[vecin].end(),nod));
}

void solve() {

    int nod,vecin;
    ok=validare_ciclu_eulerian();
    if(ok==1) {
        Stack.push(1);
        while(!Stack.empty()) {
            nod=Stack.top();
            if(v[nod].size()) {
                vecin=v[nod].front();
                Stack.push(vecin);
                sterge_muchie(nod,vecin);
            }
            else {
            Answer.push_back(Stack.top());
            Stack.pop();
            }
        }
    }

}

void afisare(){

    ofstream out("ciclueuler.out");
    int i;
    if(ok==0)
        out<<-1;
    else
        for(i=1;i<Answer.size();i++)
            out<<Answer[i]<<' ';
    out<<'\n';
    out.close();

}

int main () {

    citire();
    solve();
    afisare();
    return 0;

}