Cod sursa(job #2252242)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 2 octombrie 2018 17:05:34
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100005

int Grad[ NMAX ];
stack < int > Q;
vector < list < int > > V(NMAX );

void stergere ( int x, int y ) {

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

    V[ x ].erase( find( V[ x ].begin(), V[ x ].end(), y ) );
    V[ y ].erase( find( V[ y ].begin(), V[ y ].end(), x ) );


}

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_front( y );
        V[ y ].push_front( 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 ) printf( "%d ", nod );
            Q.pop();
        } else {
            fiu = V[ nod ].front();
            Q.push( fiu );
            stergere( nod, fiu );
        }
    }


    return 0;
}