Cod sursa(job #657836)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 7 ianuarie 2012 15:11:31
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
 # include <fstream>
 # include <vector>
 # include <deque>
 
 # define dim 100005
 # define pb push_back
 
 using namespace std;
 
 ifstream f("ciclueuler.in");
 ofstream g("ciclueuler.out");
 
 vector < int > a[ dim ], sol;
 deque < int > q;
 
 bool mc[ dim ];
 int ok = 1;
 int n, m;
 
 
 void euler( int nod )
 {
	 int nod2;
	 
	 q.push_front( nod );
	 
	 while( !q.empty() )
	 {
		 nod = q.front();
		 
		 if ( a[ nod ].size() == 0 )
		 {
			 sol.pb( nod );
			 q.pop_front();
			 continue;
		 }
		 
		 nod2 = a[ nod ].back();
		 a[ nod ].pop_back();
		 q.push_front( nod2 );
		 

		 for (  vector < int > :: iterator it = a[ nod2 ].begin() ; it != a[ nod2 ].end() ; ++it )
			 if (  *it == nod )
			 {
				 a[ nod2 ].erase( it );
				 break;
			 }
	 }
 }
 
 
 void citire()
 {
	 int i, x, y;
	 
	 f >> n >> m;
	 for ( i = 1 ; i <= m ; ++i )
	 {
		 f >> x >> y;
		 a[ x ].pb( y );
		 a[ y ].pb( x );
	 }
	 
 }
 
 void afisare()
 {
	 int i, j;
	 /*for ( i = 1 ; i <= n ; i++ )
	 {
		 for ( j = 0 ; j < a[ i ].size() ; j++ )
			 g << a[ i ][ j ] << " ";
		 g << "\n";
	 }*/
	 for ( vector < int > :: iterator it = sol.begin() ; it != sol.end() ; ++it )
		 g << ( *it ) << " ";
 }
 
 void rezolva()
 {
	 int i;
	 for ( i = 1 ; i <= n && ok ; i++ )
		 if ( a[ i ].size() % 2 == 1 )
			 ok = 0;
		 
		 if ( ok == 0 )
			 g << -1 ;
		 else
			 euler( 1 );
 }
 
 int main()
 {
	 citire();
	 rezolva();
	 afisare();
	 return 0;
 }