Cod sursa(job #795712)

Utilizator veleanduAlex Velea veleandu Data 9 octombrie 2012 15:13:14
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

    #define pb push_back
    #define fi first
    #define se second
    #define max_n 100005
    #define max_m 500005

    vector <int> V[max_n];
    int n,m,a,b,i;
    pair<int,int> Mu[max_m];
    bool Nr[max_n];
    bool Viz_m[max_m];
    bool Viz[max_n];
    int Rez[max_m],rez;
    vector<int> :: iterator It[max_n];

    void df ( int nod )
    {
        for ( ; It[nod] != V[nod].end();   )
        {
            int M=*It[nod];
            It[nod]++;
            if ( !Viz_m[ M ] )
            {
                Viz_m[ M ]=1;
                df ( Mu [ M ].fi+ Mu [ M ].se- nod );
            }
        }
        Rez[ ++rez ]=nod;
        Viz[ nod ]=1;
    }

int main()
{
    freopen ("ciclueuler.in","r",stdin);
    freopen ("ciclueuler.out","w",stdout);

    scanf ("%d %d", &n, &m );
    for ( i=1; i<=m; i++ )
    {
        scanf ("%d %d ", &a, &b );
        Mu[i].fi=a;
        Mu[i].se=b;
        V[a].pb(i);
        V[b].pb(i);

        Nr[a]^=1;
        Nr[b]^=1;
    }

    for ( i=1; i<=n; i++ )
        It[i]= V[i].begin();
    for ( i=1; i<=n; i++ )
        if ( Nr[i] )
        {
            printf("-1\n");
            return 0;
        }

    df(1);
    for ( i=1; i<=n; i++ )
        if ( !Viz[ i ] )
        {
            printf("-1\n");
            return 0;
        }
    for ( i=1; i<rez; i++ )
        printf("%d ",Rez[i]);

    return 0;
}