Cod sursa(job #632592)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 11 noiembrie 2011 18:37:17
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#define N 100003

using namespace std;

int n, m, sol[N], k;

struct nod
{
    int x;
    nod *urm;
} *a[N];

void add(nod *&p, int x)
{
    nod *q = new nod;
    q -> x = x;
    q -> urm = p;
    p = q;
}

void citire()
{
    scanf ("%d %d ", &n, &m);
    for (int i = 1; i <= m; ++ i)
    {
        int x, y;
        scanf ("%d %d ", &x, &y);
        add (a[x], y);
        add (a[y], x);
    }
}

bool grade()
{
    for (int i = 1; i <= n; ++ i)
    {
        int nr = 0;
        for (nod *j = a[i]; j; ++nr, j = j -> urm);
        if (nr % 2 != 0)
            return 0;
    }
    return 1;
}

void afisare()
{
    for (int i = 0; i < k - 1; ++ i)
        printf ("%d ", sol[i]);
    printf ("\n");
}

void euler(int i)
{
    for (nod *j = a[i]; j; j = j -> urm)
        if (j -> x > 0)
        {
            int aux = j -> x;
            j -> x = 0;
            for (nod *l = a[aux]; l; l = l -> urm)
                if (l -> x == i)
                {
                    l -> x = 0;
                    break;
                }
            euler (aux);
        }
    sol[k ++] = i;
}

int main()
{
    freopen ("ciclueuler.in", "r", stdin);
    freopen ("ciclueuler.out", "w", stdout);
    citire();
    if (!grade())
        printf ("-1\n");
    else
    {
        euler (1);
        afisare();
    }
    return 0;
}