Cod sursa(job #1337445)

Utilizator BLz0rDospra Cristian BLz0r Data 9 februarie 2015 00:25:55
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
using namespace std;

#define Nmax 100002

FILE *f = fopen ( "ciclueuler.in", "r" );
FILE *g = fopen ( "ciclueuler.out", "w" );

vector < int > G[Nmax];
stack < int > S;
queue < int > Q;

int N, M, visited, grad[Nmax];
bool inQ[Nmax], viz[Nmax];

void BFS ( int start ){
	int nod;
	vector < int > :: iterator it;
	
	Q.push( start );
	inQ[start] = 1;
	
	while ( !Q.empty() ){
		nod = Q.front();
		Q.pop();
		viz[nod] = 1; visited++;
		inQ[nod] = 0;
		
		for ( it = G[nod].begin(); it < G[nod].end(); ++it )
			if ( !viz[*it] && !inQ[*it] ){
				Q.push( *it );
				inQ[*it] = 1;
			}
	}
	
}

bool eulerian (){
	
	for ( int i = 1; i <= N; ++i )
		if ( grad[i] & 1 ) 
			return 0;
	
	return 1;
}

void sterge ( int x, int y ){
	vector < int > :: iterator it;
	
	for ( it = G[x].begin(); it < G[x].end(); ++it ){
		if ( *it == y ){
			G[x].erase ( it );
			break;
		}
	}
	
	for ( it = G[y].begin(); it < G[y].end(); ++it ){
		if ( *it == x ){
			G[y].erase ( it );
			break;
		}
	}
}
	
void Euler ( int nod ){
	vector < int > :: iterator it;
	int aux;
	
	for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
		aux = *it;
		sterge ( nod, aux ); 
		Euler ( aux );
	}
	
	S.push ( nod );
}

void afisare (){

	while ( S.size() > 1 ){
		fprintf ( g, "%d ", S.top() );
		S.pop();
	}
	S.pop();
}

int main(){
	int x, y;
	
	fscanf ( f, "%d%d", &N, &M );
	
	for ( int i = 1; i <= M ;++i ){
		fscanf ( f, "%d%d", &x, &y );
		G[x].push_back ( y );
		G[y].push_back ( x );
		
		grad[x]++;
		grad[y]++;
	}
	
	BFS ( 1 );
	
	if ( visited == N && eulerian () ){
		Euler ( 1 );
		afisare ();
	}
	else
		fprintf ( g, "-1" );
		
	return 0;
}