Cod sursa(job #772393)

Utilizator danalex97Dan H Alexandru danalex97 Data 29 iulie 2012 14:26:35
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

#define Nmax 100011

typedef vector<int>::iterator Iter;

vector<int> Leg[Nmax];
int Grad[Nmax];
int Marked[Nmax];
int N,M;

vector<int> Rez;
queue<int> Stiva;

void Get( int Nod )
{
	Marked[Nod]=1;
	for ( Iter it=Leg[Nod].begin() ;it!=Leg[Nod].end() ;++it )
		if ( !Marked[ *it ] )
			Get( *it );
}

void Erase( int v, int w )
{
    --Grad[v];
    --Grad[w];
	
	for ( Iter it = Leg[v].begin(),it2 = Leg[v].begin()+1; it2 != Leg[v].end(); ++it,++it2)
		swap( *it , *it2 );
	Leg[v].pop_back();
    
	for ( Iter it = Leg[w].begin(); it != Leg[w].end(); ++it)
        if( *it == v ) 
		{
			for (Iter it2 = Leg[w].begin(),it3 = Leg[w].begin()+1; it2 != Leg[w].end()-1; ++it2,++it3)
				swap( *it2 , *it3 );
			Leg[w].pop_back();
            break;
        }
}

void Euler( int v )
{	
	while ( Leg[v].size() )
	{
		int w = Leg[v].front();
		Stiva.push( v );
		Erase( v , w );
		v = w;
	}
}

void Solve()
{
	int v=1;
	Stiva.push( v );
	
	do 
	{
		Euler( v );
		
		v=Stiva.front();
		Stiva.pop();
		
		Rez.push_back( v );
	}
	while ( Stiva.size() );
}

int main()
{
	F>>N>>M;
	for (int i=1;i<=M;++i)
	{
		int x,y;
		F>>x>>y;
		Leg[x].push_back( y );
		if ( x != y ) Leg[y].push_back( x );
		++Grad[x];
		++Grad[y];
	}
	
	Get( 1 );
	for (int i=1;i<=N;++i)
		if ( Grad[i]%2 || !Grad[i] || !Marked[i] )
		{
			G<<"-1\n";
			return 0;
		}
	
	Solve();
	
	for (; Rez.size()>1 ;Rez.pop_back() )
		G<<Rez.back()<<' ';
	G<<'\n';
}