Cod sursa(job #795819)

Utilizator veleanduAlex Velea veleandu Data 9 octombrie 2012 18:24:29
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <vector>
#include <cstdio>
using namespace std;

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

    int n,m;
    int i,a,b;
    vector <int> :: iterator It[max_n];
    vector <int> V[max_n];
    vector <int> Rez;

    pair<int,int> Mu[max_m];
    bool Viz_m[max_m];

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

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);
    }
    for ( i=1; i<=m; i++ )
    {
        if ( V[i].size()%2 )
        {
            printf("-1\n");
            return 0;
        }
    }

    for ( i=1; i<=n; i++ )
        It[i]=V[i].begin();

    euler(1);

    for ( i=1; i<Rez.size(); i++ )
         printf("%d ", Rez[i] );

    return 0;
}