Cod sursa(job #430928)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 31 martie 2010 14:37:23
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
#include<vector>
using namespace std;
int n,m,x[500002],y[500002],viz[100002],sol[500002],g[100002];
vector<int> v[100002];

void dfs(int nod)
{
    for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
        if(!viz[*it])
        {
            viz[*it]=1;
            dfs(x[*it]+y[*it]-nod);
        }
    sol[++sol[0]]=nod;
}

int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d%d",&n,&m);
    int i;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        v[x[i]].push_back(i);
        v[y[i]].push_back(i);
        g[x[i]]++;
        g[y[i]]++;
    }
    for(i=1;i<=n;i++)
        if(g[i]&1)
        {
            printf("-1\n");
            return 0;
        }
    dfs(1);
    while(sol[0]>1)
        printf("%d ",sol[sol[0]--]);
    return 0;
}