Cod sursa(job #533652)

Utilizator andu04Popa Andi andu04 Data 14 februarie 2011 12:49:52
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <list>
#include <stdio.h>

using namespace std;
int n,m,N,c[500001];

list<int> G[100001];

void euler(int nod)
{
    list<int>::iterator it,jt;
    int x;
    it=G[nod].begin();
    while(it!=G[nod].end())
    {
        x=*it;
        jt=G[*it].begin();
        while (jt!=G[*it].end())
        {
            if (*jt==nod)
                {
                    G[*it].erase(jt);
                    break;
                }
            jt++;
        }
        G[nod].pop_front();
        euler(x);
        it=G[nod].begin();
    }
    c[++N]=nod;
}

int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf ("%d%d",&n,&m);
    int x,y;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for (int i=1;i<=n;i++)
        if (G[i].size()%2)
        {
            printf("-1");
            return 0;
        }
    euler(1);
    for (int i=N;i>1;i--)
        printf("%d ",c[i]);

    return 0;
}