Cod sursa(job #632135)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 10 noiembrie 2011 13:59:42
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <cstdio>
#define N 100003

using namespace std;

int n, m, viz[N], mic[N], mare[N], k, l;

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);
        if (x != y)
        {
            add (a[x], y);
            add (a[y], x);
        }
    }
}

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

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;
}

bool izolat(int i)
{
    bool ok = 0;
    for (nod *j = a[i]; j; ok = 1, j = j -> urm)
    return ok;
}

void euler(int i)
{
    for (nod *j = a[i]; j; )
    {
        int aux = j -> x;
        nod *ceva = j;
        j = j -> urm;
        delete ceva;
        euler (aux);
    }
    mic[l ++] = i;
}

void ciclu()
{
    for (int i = 1; i <= n; ++ i)
        if (!izolat (i))
        {
            euler (i);
            return;
        }
}

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