Cod sursa(job #2252237)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 2 octombrie 2018 16:55:20
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

#define NMAX 100005

int Grad[ NMAX ];
stack < int > Q;
vector < int > S, V[ NMAX ];

void stergere ( int x, int y ) {

    Grad[ x ]--; Grad[ y ]--;

    V[ x ].pop_back();

    vector < int > :: iterator it;
    for ( it = V[ y ].begin(); it != V[ y ].end(); ++it ) {
        if ( x == *it ) {
            V[ y ].erase( it );
            return ;
        }
    }


}

int main () {

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

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

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

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

    Q.push( 1 );
    while ( !Q.empty() ) {
        nod = Q.top();
        if ( Grad[ nod ] == 0 ) {
            if( Q.size() > 1 ) S.push_back( nod );
            Q.pop();
        } else {
            fiu = V[ nod ][ Grad[ nod ] - 1 ];
            Q.push( fiu );
            stergere( nod, fiu );
        }
    }

    vector < int > :: iterator it;
    for ( int i  = 0; i < S.size(); ++i ) {
        printf( "%d ", S[ i ] );
    }

    return 0;
}