Cod sursa(job #544222)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 1 martie 2011 11:01:15
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<stdio.h>
#define N 100005
struct Nod {
    int x;
    Nod *next;
};
int n, m;
int list[N];
int gr[N];
int viz[N];
Nod* a[N];
void insert(Nod *&p, int q) {
    Nod* t = new Nod();
    t -> x = q;
    t -> next = p;
    p = t;
}
void find_tour(int s) {
    for(Nod *it = a[s]; it; it = it -> next)
     if (it -> x != -1) {
        int n = it -> x;
        for(Nod* it2 = a[it -> x]; it2 != 0; it2 = it2 -> next)
         if (it2 -> x == s) {it2 -> x = -1; break;}
        it -> x = -1;
        find_tour(n);
    }
    list[++list[0]] = s;
}
int df(int s) {
    viz[s] = 1;
    for(Nod *it = a[s]; it; it = it -> next)
     if (!viz[it->x])
      df(it->x);
}
int este_conex() {
    df(1);
    for(int i = 1; i <= n; i++)
     if (viz[i] == 0) return 0;
    return 1;
}
int grad_par() {
    for(int i = 1; i <= n; i++)
     if (gr[i] % 2 != 0) return 0;
    return 1;
}
int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= m; i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        gr[u]++;
        gr[v]++;
        insert(a[u], v);
        insert(a[v], u);
    }
    if (este_conex() && grad_par()) {
        find_tour(1);
        for(int i = 1; i < list[0]; i++)
            printf("%d ",list[i]);
        printf("\n");
    }
    else
     printf("-1\n");
    return 0;
}