Cod sursa(job #281174)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 13 martie 2009 21:11:50
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <list>
using namespace std;

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

#define MAX 100010 
typedef list<int> li;
li G[MAX];
int Grad[MAX], U[MAX], N, M;


void DF( int n ) {
	U[n] = true;
	for ( li::iterator i=G[n].begin(); i!=G[n].end(); ++i )
		if ( ! U[*i] ) DF(*i);
}



void euler( int n ) {
	for ( li::iterator i=G[n].begin(); i!=G[n].end(); ++i ) {
		if ( *i==-1 ) continue;
		int x = *i;
		*i = -1;
		for ( li::iterator j=G[x].begin(); j!=G[x].end(); ++j ) 
			if ( *j==n ) { *j = -1; break; }
		euler( x );
	}
	out << n << " ";
}

int main() {
	// load
	in >> N >> M;
	while ( M-- ) {
		int x, y;
		in >> x >> y;
		G[x].push_back( y ); Grad[x] ++;
		G[y].push_back( x ); Grad[y] ++;
	}
	// tests
	DF( 1 );
	for ( int i=1; i<=N; ++i ) 
		if ( U[i]==false || Grad[i]%2==1 ) {
			out << "-1\n";
			return 0;
		}
	// concret
	euler(1);
	out << endl;
	return 0;
}