Cod sursa(job #1601966)

Utilizator Master011Dragos Martac Master011 Data 16 februarie 2016 13:38:49
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<cstdio>
using namespace std;

const int nMax = 100000, mMax = 500000;
int muchie[mMax * 2 + 1], nodV[mMax * 2 + 1], urm[mMax * 2 + 1], lst[nMax + 1], sol[mMax + 1];
bool viz[nMax], ut[mMax + 1], grad[nMax + 1];
int nr = 0, nrS = 0;

FILE *in, *out;

inline void adauga(int i, int x, int y){
    nodV[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
    muchie[nr] = i;
}

void dfs(int nod){
    viz[nod] = true;
    int pos = lst[nod], vec = nodV[pos];
    while(pos){
        if(!ut[muchie[pos]]){
            ut[muchie[pos]] = true;
            dfs(vec);
        }

        pos = urm[pos];
        vec = nodV[pos];
    }
    sol[++nrS] = nod;
}

int main (){
    in = fopen("ciclueuler.in","r");
    out = fopen("ciclueuler.out","w");

    int n, m; fscanf(in,"%d%d", &n, &m);
    for(int i = 1, x, y; i <= m ; ++i){
        fscanf(in,"%d%d", &x, &y);
        adauga(i, x, y);
        adauga(i, y, x);

        grad[x] = 1 - grad[x];
        grad[y] = 1 - grad[y];
    }


    dfs(1);

    for(int i = 1 ; i <= n ; ++i){
        if(!viz[i] || grad[i]){
            fprintf(out,"-1\n");
            return 0;
        }
    }


    for(int i = 1 ; i < nrS ; ++i)
        fprintf(out,"%d ", sol[i]);
    fprintf(out,"\n");
    return 0;
}