Cod sursa(job #430941)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 31 martie 2010 14:50:11
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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];

inline 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",&n,&m);
    int i,j;
    char s[20];
    for(i=1;i<=m;i++)
    {
        gets(s);
        for(j=0;s[j]!=' ';j++)
            x[i]=x[i]*10+s[j]-'0';
        for(++j;s[j];j++)
            y[i]=y[i]*10+s[j]-'0';
//        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;
}