Cod sursa(job #772375)

Utilizator danalex97Dan H Alexandru danalex97 Data 29 iulie 2012 13:42:09
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(); it != Leg[v].end(); ++it)
        if( *it == w ) 
		{
			swap( *it , Leg[v].back() );
            Leg[v].pop_back();
            break;
        }
    
	for ( Iter it = Leg[w].begin(); it != Leg[w].end(); ++it)
        if( *it == v ) 
		{
			swap( *it , Leg[w].back() );
            Leg[w].pop_back();
            break;
        }
}

void Euler( int v )
{	
	while ( 1 )
	{
		if ( Leg[v].empty() )
			break;
		int w = Leg[v].front();
		Rez.push_back( 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() ;Rez.pop_back() )
		G<<Rez.back()<<' ';
	G<<'\n';
}