Cod sursa(job #1923008)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 10 martie 2017 20:14:41
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <list>
using namespace std;

#define NMAX 100001

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

void StergeMuchie ( int x, int y ) {

    vector < int > :: iterator it;
    V[ x ].pop_back();

    for ( it = V[ y ].begin(); it != V[ y ].end(); ++it ) {
        if ( *it == x ) {
            V[ y ].erase( it );
            return ;
        }
    }


}

int main () {

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

    int n, m, i, j, x, y, s, k, 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;
        }
    }

    S.push( 1 );
    while ( !S.empty() ) {
        nod = S.top();
        if ( Grad[ nod ] == 0 ) {
            if ( S.size() > 1 ) printf( "%d ",nod );
            S.pop();
        } else {
            fiu = V[ nod ][ V[ nod ].size() - 1 ];
            StergeMuchie( nod, fiu );
            Grad[ nod ]--; Grad[ fiu ]--;
            S.push( fiu );
        }
    }


    return 0;
}