Cod sursa(job #431354)

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

void read()
{
    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]<<3)+(x[i]<<1)+s[j]-'0';
        for(++j;s[j];j++)
            y[i]=(y[i]<<3)+(y[i]<<1)+s[j]-'0';
        v[x[i]].push_back(i);
        v[y[i]].push_back(i);
    }
}

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

int main()
{
    read();
    for(int i=1;i<=n;i++)
        if(v[i].size()&1)
        {
            printf("-1\n");
            return 0;
        }
    dfs(1);
    while(sol[0]>1)
        printf("%d ",sol[sol[0]--]);
    return 0;
}