Cod sursa(job #1758164)

Utilizator din99danyMatei Daniel din99dany Data 16 septembrie 2016 17:56:00
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

#define NMAX 100006

vector < int > v[ NMAX ];
stack < int > Q;
int deg[ NMAX ];

void sterge( int n, int k ){

    vector < int > :: iterator it;

    for( it = v[ n ].begin(); it != v[ n ].end(); ++it ){
        if( *it == k ){
            deg[ *it ]--;
            v[ n ].erase( it );
            return ;
        }
    }

}

int main()
{

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

    int n, m, i, j, x, y, nod;

    scanf("%d%d",&n,&m);
    while( m-- ){
        scanf("%d%d",&x,&y);
        v[ x ].push_back( y ); v[ y ].push_back( x );
        deg[ x ]++;
        deg[ y ]++;
    }

    for( i = 1; i <= n; ++i )
        if( deg[ i ] % 2 == 1 ){
            printf("-1\n");
            return 0;
        }

    Q.push( 1 );
    while( !Q.empty() ){
        nod = Q.top();
        if( !deg[ nod ] ){
            if( Q.size() > 1 ) printf("%d ",nod);
            Q.pop();
        }
        else{
            Q.push( v[ nod ][ 0 ] );
            sterge( v[ nod ][ 0 ], nod );
            v[ nod ].erase( v[ nod ].begin() );
            deg[ nod ]--;
        }
    }

    return 0;

}