Cod sursa(job #419962)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 18 martie 2010 11:29:01
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <stdio.h>
#include <list>
#define IN "ciclueuler.in"
#define OUT "ciclueuler.out"
#define Lg 500005
#define Lg1 100005

using namespace std;

list <int> L[Lg];
list <int> :: iterator IT;
int poz,N,M;
int Grad[Lg],Sir[Lg];

void Read()
{
    int a,b;
    scanf ("%d %d",&N,&M);
    for (int i=0;i<M;i++)
    {
        scanf ("%d %d",&a,&b);
        Grad[a]++;
        Grad[b]++;
        L[a].push_back(b);
        L[b].push_back(a);
    }
}

void Solve()
{
    for (int i=1;i<=N;i++)
        if (Grad[i]%2==1)
        {
            printf("-1\n");
            return ;
        }
    int Top,Nod;
    Sir[poz=1]=1;
    while(poz)
    {
        Nod=Sir[poz];
        if (!L[Nod].empty())
        {
            Top=L[Nod].front();
            L[Nod].pop_front();
            for (IT=L[Top].begin() ; IT!=L[Top].end() && *IT!=Nod; IT++);
            L[Nod].erase(IT);
            Sir[++poz]=Top;
        }
        else
            printf("%d ",Sir[poz--]);
    }

    printf("\n");
}

int main ()
{
    freopen (IN ,"r", stdin);
    freopen (OUT ,"w", stdout);
    Read();
    Solve();
    return 0;
}