Cod sursa(job #531938)

Utilizator skullLepadat Mihai-Alexandru skull Data 10 februarie 2011 17:05:26
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>
#include <list>
using namespace std;
#define nmax 100005
#define mx 500005

list<int> G[nmax];
int sol[nmax];
int N, nr;

void citire ()
{
    int M, i, x, y;
    freopen("ciclueuler.in","r",stdin);
    scanf("%d%d", &N, &M);
    for (i = 1; i <= M; ++i)
    {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void euler(int nod)
{
    int x;
    list<int>::iterator it,jt;
    it = G[nod].begin();
    for ( ; it!=G[nod].end() ; )
    {
        x = *it;
        jt = G[*it].begin();
        for ( ; jt != G[*it].end(); )
        {

            if (*jt == nod)
            {
                G[*it].erase(jt);
                break;
            }
            jt++;
        }
        G[nod].pop_front();
        euler(x);
        it = G[nod].begin();
    }
    sol[++nr] = nod;
}

void afisare ()
{
    int i;
    for (i = nr; i > 1; --i) printf("%d ", sol[i]);
}

int main ()
{
    int i;
    citire ();
    freopen("ciclueuler.out","w",stdout);
    for (i = 1; i <= N; ++i)
        if ( G[i].size()%2 ) { printf("-1\n"); return 0; }
    nr = 0;
    euler(1);
    afisare ();
    return 0;
}