Cod sursa(job #1377545)

Utilizator superman_01Avramescu Cristian superman_01 Data 5 martie 2015 22:28:04
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>

#define NMAX 100005
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)<(b)?(a):(b))

using namespace std;

ifstream in ( "ciclueuler.in" );
ofstream out ( "ciclueuler.out" );
bool used[NMAX] ;
vector < int > G[NMAX] , Sol;
stack  < int > S ;
int N , M , number ;

void DFS ( int node ){
  used[node] = true;
  ++number;
  for ( vector < int > ::iterator it = G[node].begin () ; it != G[node].end() ; ++it )
                if ( !used[node] )
                    DFS ( node );
}
bool EulerGraph ( void ){
    int i , j ;
    DFS ( 1 );
    if ( number != N ) return 0;
    for ( i = 1 ; i <= N ; ++i )
       if  ( G[i].size()&1 ) return 0 ;
    return 1 ;
}
void EdgeDelete ( int X , int Y ){
    G[X].erase(G[X].begin());
    for (vector < int > ::iterator it = G[Y].begin () ; it != G[Y].end() ; ++it )
        if( *it == X){
          G[Y].erase(it);
          return ;

        }


}


void Euler ( int node ) {
   int newnode ;
    while ( G[node].size() ){
     newnode = G[node].front();
     S.push(node);
     EdgeDelete ( node , newnode );
     node = newnode;
    }
}


int main ( void ){
   int i , j , x, y ;
   in >> N >> M ;
   for ( i = 1 ; i <= M ; ++i ){
      in >> x >> y ;
      G[x].push_back(y) ;
      G[y].push_back(x) ;
   }
   if ( !EulerGraph() ){
    out << "-1\n";
   }else{
    int node = 1 ;
    do {
      Euler( node );
      node = S.top() , S.pop();
      Sol.push_back(node);
    }while ( !S.empty());
   }
   for ( vector < int > ::iterator it  = Sol.begin() ; it != Sol.end() ; ++it )
   out << *it << " " ;
   in.close();
   out.close();
   return 0 ;
}