Cod sursa(job #476349)

Utilizator MciprianMMciprianM MciprianM Data 10 august 2010 19:21:56
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 100009;

vector <int> G [ MAXN ];
int deg [ MAXN ], n, m;
stack <int> cycleNode, s;

void Euler (){

    int n = 1, e;

    do{
        if ( G [ n ] . size () == 0 ){
            cycleNode . push ( n );
            n = s . top ();
            s . pop ();
        }
        else{
            e = G [ n ] . back ();
            G [ n ] . pop_back ();
            for ( vector<int>::iterator it = G [ e ] . begin (); it != G [ e ] . end (); ++ it )
                if ( * it == n ){
                    G [ e ] . erase ( it );
                    break;
                }
            s . push ( n );
            n = e;
        }
    }while ( ! s . empty () );


}

int main(){

    int i, x, y;

    ifstream f ("ciclueuler.in");
    ofstream g ("ciclueuler.out");

    f >> n >> m;

    while (m --){
        f >> x >> y;
        G [ x ] . push_back ( y );
        G [ y ] . push_back ( x );
        ++ deg [ x ];
        ++ deg [ y ];
    }

    f . close ();

    for ( i = 1; i <= n; ++ i )
        if ( deg [ i ] & 1 ){
            g << "-1\n";
            g . close ();
            return 0;
        }

    Euler ( );

    g << "1 ";

    while ( ! cycleNode . empty ()  ){
        g << cycleNode . top () << " ";
        cycleNode . pop();
    }

    g . close ();

    return 0;

}