Cod sursa(job #668985)

Utilizator valentina506Moraru Valentina valentina506 Data 25 ianuarie 2012 22:13:07
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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()
{
 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;
}