Cod sursa(job #477186)

Utilizator MciprianMMciprianM MciprianM Data 13 august 2010 18:42:57
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <bitset>

using namespace std;

vector < int > G [ 100001 ];
int deg [ 100001 ];
bitset <100001> u;
int n, m;
stack <int> c, s;

bool pare (){

    for ( int i = 1; i <= n; ++ i )
        if ( deg [ i ] & 1 )
            return false;
    return true;

}

void euler (int n){

    //cout << n << "\n";

    vector < int > :: iterator i;
    int e;

    do{
        if ( G [ n ] . size () == 0 ){
            c . push ( n );
            n = s . top (  );
            s.pop();

        }
        else{
            e = G [ n ] . back ();//muchia
            u [ e ] = true;
            G [ n ] . pop_back ();
            for ( i = G [ e ] . begin (); i != G [ e ] . end (); ++ i )
                if ( *i == n ){
                    G [ e ] . erase ( i );
                    break;
                }
            s . push (n);
            n = e;
        }
    }while ( !s.empty() );
}

void print ( ofstream *g ){
    while ( ! c . empty () ){
        * g << c . top () << " ";
        c . pop ();
    }
    * g << "\n";
}

int main()
{

    int i, x, y;
    ifstream f ( "ciclueuler.in" );
    ofstream g ( "ciclueuler.out" );
    f >> n >> m;
    for ( i = 0; i < m; ++ i ){
        f >> x >> y;
        ++ deg [ x ];
        ++ deg [ y ];
        G [ x ] . push_back ( y );
        G [ y ] . push_back ( x );
    }
    f.close();

    if ( !pare () ){
        g << "-1\n";
        g . close();
        return 0;
    }
    else{
        u [ 1 ] = true;
        euler(1);
        for ( i = 1; i <= n; ++ i )
            if ( ! u [ i ] ){
                g << "-1\n";
                g . close();
                return 0;
            }
        print(&g);
        g . close();
    }

    return 0;
}