Cod sursa(job #476574)

Utilizator MciprianMMciprianM MciprianM Data 11 august 2010 16:52:20
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <bitset>

using namespace std;

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

void bfs (){

    int i, n, t;

    q . push ( 1 );
    u . set ( 1 );

    while ( ! q . empty () ){
        n = q . front ();
        q . pop ();
        t = G [ n ] . size ();
        for ( i = 0; i < t; ++ i )
            if ( ! u [ G [ n ] [ i ] ] ){
                q . push ( G [ n ] [ i ] );
                u . set ( G [ n ] [ i ] );
            }
    }

}

bool connected (){

    bfs (  );

    for ( int i = 1; i <= n; ++ i )
        if ( ! u [ i ] )
            return false;

    return true;

}

bool eulerian (){

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

}

void euler (int n){

    vector < int > :: iterator i;

    int e;
    if ( G [ n ] . size () == 0 ){
        c . push ( n );
        return;
    }
    e = G [ n ] . back ();//muchia
    G [ n ] . pop_back ();
    for ( i = G [ e ] . begin (); i != G [ e ] . end (); ++ i )
        if ( *i == n ){
            G [ e ] . erase ( i );
            break;
        }
    euler ( e );
    c . push ( n );
    return;
}

void print ( ofstream *g ){
    c.pop();
    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 ( !eulerian () ){
        g << "0\n";
        g . close();
        return 0;
    }
    else{
        euler(1);
        print(&g);
        g . close();
    }

    return 0;
}