Cod sursa(job #409094)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 3 martie 2010 14:01:41
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.37 kb
#include <algorithm>
#include <bitset>
#include <stack>
#include <vector>
using namespace std;

#define MAX_N 100005
#define MAX_S 10005

char s[ MAX_S ];
int N, M;
int cnt_s, g[ MAX_N ];
bitset <MAX_N> f;
stack <int> stv;
vector <int> sol, v[ MAX_N ];

void df( const int &nod ) {

    vector <int> :: iterator it;

    f[ nod ] = true;

    for( it = v[ nod ].begin(); it != v[ nod ].end(); ++it )
        if( f[ *it ] == false )
            df( *it );
}

void rem( const int &x, const int &y ) {

    vector <int> :: iterator it;

    for( it = v[ x ].begin(); it != v[ x ].end(); ++it )
        if( *it == y ) {

            *it = v[ x ][ v[ x ].size() - 1 ];
            v[ x ].pop_back();

            break;
        }
}

void euler( int nod ) {

    int aux;

    while( true ) {

        if( v[ nod ].empty() )
            break;

        aux = v[ nod ].back();
        stv.push( aux );

        rem( nod, aux );
        rem( aux, nod );

        nod = aux;
    }
}

void read( int &val ) {

    while( !isdigit( s[ cnt_s ] ) )
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }

    val = 0;
    while( isdigit( s[ cnt_s ] ) ) {

        val = val*10 + s[ cnt_s ] - '0';
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }
    }
}

int main() {

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

    int i, x, y, nod;
    vector <int> :: iterator it;

    cnt_s = MAX_S - 1;

    read( N );
    read( M );

    while( M-- ) {

        read( x );
        read( y );

        ++g[ x ];
        ++g[ y ];

        v[ x ].push_back( y );
        v[ y ].push_back( x );
    }

    for( i = 1; i <= N; ++i )
        if( g[ i ] & 1 ) {

            printf( "-1" );
            return 0;
        }

    df( 1 );
    for( i = 1; i <= N; ++i )
        if( f[ i ] == false ) {

            printf( "-1" );
            return 0;
        }

    stv.push( 1 );
    do {

        nod = stv.top();
        stv.pop();
        euler( nod );

        if( !stv.empty() )
            sol.push_back( stv.top() );
    }
    while( !stv.empty() );

    for( it = sol.begin() + 1; it != sol.end(); ++it )
        printf( "%d ", *it );

    return 0;
}