Cod sursa(job #1451372)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 16 iunie 2015 21:32:25
Problema Ciclu Eulerian Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.3 kb
#include <stdio.h>
#define MAXN 100000
#define MAXM 500000
FILE *fin, *fout;
int folosit[MAXM], val[2*MAXN], st[2*MAXM], dr[2*MAXM], lista[MAXN+1], nr[MAXN+1], k;
inline void adauga(int x, int y){
    val[++k]=y;
    st[k]=lista[x];
    dr[st[k]]=k;
    lista[x]=k;
    nr[x]++;
}
void euler(int nod){
    while(lista[nod]!=0){
        if(folosit[(lista[nod]-1)/2]==0){
            folosit[(lista[nod]-1)/2]=1;
            st[dr[lista[nod]]]=st[lista[nod]];
            dr[st[lista[nod]]]=dr[lista[nod]];
            euler(val[lista[nod]]);
        }else{
            st[dr[lista[nod]]]=st[lista[nod]];
            dr[st[lista[nod]]]=dr[lista[nod]];
        }
        lista[nod]=st[lista[nod]];
    }
    fprintf(fout, "%d ", nod);
}
int main(){
    int n, m, i, a, b, f, start;
    fin=fopen("ciclueuler.in", "r");
    fout=fopen("ciclueuler.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=0; i<m; i++){
        fscanf(fin, "%d%d", &a, &b);
        adauga(a, b);
        adauga(b, a);
    }
    f=1;
    for(i=1; i<=n; i++){
        if(nr[i]%2==1){
            f=0;
        }
        if(nr[i]>0){
            start=i;
        }
    }
    if(f==0){
        fprintf(fout, "-1\n");
    }else{
        euler(start);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}