Cod sursa(job #702992)

Utilizator arch_enemyAngela Gossow arch_enemy Data 2 martie 2012 10:22:04
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>

using namespace std;

#define NMAX 100001
#define MMAX 500001
#define pb push_back
#define mp make_pair
#define nod first
#define ind second

int N, M, i, x, y, Nod;
int Begin[NMAX];
vector< pair< int, int > > MuchiiNod[NMAX];
vector< int > Sol;
stack< int > Stiva;
bool UsedM[MMAX], Gata;

int main()
{
	freopen("ciclueuler.in", "r", stdin);
	freopen("ciclueuler.out", "w", stdout);
	
	scanf("%d%d", &N, &M );
	for( i = 1; i <= M; ++i )
	{
		scanf("%d%d", &x, &y );
		MuchiiNod[x].pb( mp( y, i ) );
		MuchiiNod[y].pb( mp( x, i ) );
	}
	for( i = 1; i <= N; ++i )
		if( MuchiiNod[i].size()&1 )
		{
			printf("-1\n");
			return 0;
		}
	
	memset( UsedM, false, sizeof(UsedM) );
	memset( Begin, 0, sizeof(Begin) );
	for( Stiva.push( 1 ); !Stiva.empty(); )
	{
		Nod = Stiva.top();
		Gata = true;
		
		for( i = Begin[Nod]; i < (int)MuchiiNod[Nod].size(); ++i )
			if( !UsedM[ MuchiiNod[Nod][i].ind ] )
			{
				UsedM[ MuchiiNod[Nod][i].ind ] = true;
				Begin[Nod] = i;
				Gata = false;
				Stiva.push( MuchiiNod[Nod][i].nod );
				break;
			}
		
		if( Gata )
		{
			Sol.pb( Stiva.top() );
			Stiva.pop();
		}
	}
	for( vector< int >::iterator it = Sol.begin() + 1; it != Sol.end(); ++it )
		printf("%d ", *it );
	
	return 0;
}