Cod sursa(job #1219819)

Utilizator vasica38Vasile Catana vasica38 Data 15 august 2014 12:36:47
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<stdio.h>

using namespace std;
typedef struct lista
        {
            int info;
            lista*next;
        }*nod;
nod a[100001];
int grad[100001],i,j,k,m,n,u;

bool grad1()
{
    for (i=1; i<=n; ++i)
        if (grad[i]%2==1) return 0;
    return 1;
}

void euler(int v, int p)
{
    int k;
    nod r;
    while (a[v])
    {
        k=a[v]->info;
        a[v]=a[v]->next;
        r=a[k];
        if (r->info==v) a[k]=a[k]->next;
            else
            {
                while (r->next->info!=v) r=r->next;
                r->next=r->next->next;
            }
        euler(k,p+1);
    }
    if (p>0) printf("%d ",v);
}

void add(int x, nod &p)
{
    nod r=new lista;
    r->info=x;
    r->next=p;
    p=r;
}
int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y;
    for (i=1; i<=m; ++i)
    {
        scanf("%d%d",&x,&y);
        ++grad[x];
        ++grad[y];
        add(x,a[y]);
        add(y,a[x]);
    }
    if (grad1()) euler(1,0);
        else printf("-1\n");
    return 0;
}