Cod sursa(job #972004)

Utilizator superman_01Avramescu Cristian superman_01 Data 10 iulie 2013 19:41:46
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<fstream>
#include<algorithm>
#include<stack>
#include<vector>

#define NMAX 100005

using namespace std;

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

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

void DepthFirstSearch ( int node )
{
	used [node] = true ; 
	++numb;
	for( vector < int > :: iterator it=G[node].begin () ; it != G[node].end() ; ++it )
		if( ! used[*it] )
			DepthFirstSearch(*it);
	
}

bool Check_Euler ( void )
{
	DepthFirstSearch(1);
	if( numb !=N )
		return 1;
	for( int i(1); i <= N ; ++i )
		if( degree[i] &1)
			return 1;
	return 0;
}
void Delete ( int father , int node )
{
	G[father].erase(G[father].begin());
	for( vector < int> :: iterator it=G[node].begin () ; it != G[node].end() ; ++it)
		if( *it == father )
		{
			G[node].erase(it);
			return ;
		}	
	
}
void Euler ( int node )
{
	int newnode;
	while( G[node].size() )
	{
		newnode=G[node].front();
		S.push(node);
		Delete(node,newnode);
		node=newnode;
	}		
}
void Solve ( void )
{
	int node;
	if( Check_Euler())
	{
		g<<-1<<"\n";
		g.close();
		return ;		
	}
	node=1;
	do
	{
		
		Euler(node);
		node=S.top();
		S.pop();
		Sol.push_back(node);
	}while(!S.empty());
	
}
void Write ( void )
{
	for( vector< int> :: iterator it =Sol.end() -1; it != Sol.begin() -1 ; --it )
		g<<*it<<" ";
	g.close();
          		
}

int main ( void )
{
	f>>N>>M;
	for(int i(1) ; i <= M ; ++i )
	{
		int x,y;
		f>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	f.close();
	Solve();
	Write();
    return 0 ;	
}