Cod sursa(job #1130240)

Utilizator superman_01Avramescu Cristian superman_01 Data 28 februarie 2014 12:03:28
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 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;

typedef vector < int > ::iterator vii;
ifstream in ( "ciclueuler.in" );
ofstream out ( "ciclueuler.out" );

stack < int > S;
vector < int > G[NMAX] , Sol ;
int N , M  , Nr_Nodes;
bool used[NMAX];

void DepthFirstSearch ( int node )
{
	used[node] = true;
	++Nr_Nodes;
	for ( vii it = G[node].begin() ; it != G[node].end() ; ++it )
		if ( !used[*it] )
			DepthFirstSearch ( *it );
}

bool CheckEuler ( void )
{
	int i ; 
	DepthFirstSearch ( 1 );
	if ( Nr_Nodes != N ) return 1;
	for ( i = 1 ; i <= N ; ++i )
		if ( G[i].size() % 2  )
			return 1 ;
	return 0 ;
}

void DeleteEdge ( int X , int  Y )
{
	for ( vii it = G[X].begin() ; it != G[X].end() ; ++it )
		if ( *it == Y )
		{
			G[X].erase( it );
			return ;
		}
}

void Euler ( int node )
{ 
	int newnode;
	while ( G[node].size() )
	{
		newnode = G[node].front();
		S.push(node);
		DeleteEdge ( 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 ( CheckEuler() )
		out << "-1\n" ;
	else
	{
		int node = 1;
		do 
		{
			Euler ( node );
			node = S.top() ; S.pop();
			Sol.push_back(node);
		}while ( !S.empty() );
	}
	reverse ( Sol.begin() , Sol.end() );
	for ( vii it = Sol.begin() ; it != Sol.end() ; ++it )
		out <<*it << " ";
	in.close();
	out.close();
	return 0 ;
}