Cod sursa(job #833800)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 13 decembrie 2012 05:08:10
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
using namespace std;
const char iname[] = "ciclueuler.in";
const char oname[] = "ciclueuler.out";
ifstream fin(iname);
ofstream fout(oname);
int N , M , i , j , nr;
int X[ 500500 ] , Y[ 500500 ] , sol[ 500500 ];
bool viz[ 500500 ];
vector < int > G[ 100100 ];
inline bool ok ()
{
	for ( i = 1; i <= N; ++i )
		if ( G[ i ].size() % 2 ) return 0;
	return 1;
}
inline void Euler ( int nod )
{
	vector < int > :: iterator it;
	for ( it = G[ nod ].begin(); it != G[ nod ].end(); ++it )
	{
		if ( !viz[ *it ] )
		{
			viz[ *it ] = true;
			Euler ( X[ *it ] + Y[ *it ] - nod );
		}
	}
	sol[ ++nr ] = nod;
}
int main()
{
	fin >> N >> M;
	for ( i = 1; i <= M; ++i )
	{
		fin >> X[ i ] >> Y[ i ];
		G[ X[ i ] ].push_back( i );
		G[ Y[ i ] ].push_back( i );
	}
	if ( ok() )
	{
		Euler( 1 );
		for ( i = 1; i <= nr; ++i ) 
			fout << sol[ i ] << ' ';
		fout << '\n';
	}
	else 
		fout << -1 << '\n';
	return 0;
}