Cod sursa(job #919964)

Utilizator veleanduAlex Velea veleandu Data 19 martie 2013 22:34:01
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>

#include <iostream>
#include <vector>
using namespace std;

#define max_n 100005
#define max_m 500005
#define pb push_back

bool VizEdge[max_m];

struct edge{
	int a,b,ind;
	edge(){
		a=b=ind=0;
	}
	edge( int _a, int _b, int _ind ){
		a=_a;
		b=_b;
		ind=_ind;
	}
 	int other( int nod ){
		return a+b-nod;
	}
	int viz(){
		return VizEdge[ind];
	}
	void setViz(){
		VizEdge[ind]=1;
	}
} Edge[max_m];
vector<int> Vertex[max_n], Rez;

int n,i;
int It[max_n];

void euler( int nod ){
	for( ; It[nod]< int( Vertex[nod].size() ); ++It[nod] ){
		#define mu Vertex[nod][It[nod]]
		Edge[mu];
		if( !Edge[mu].viz() ){
			Edge[mu].setViz();
			euler( Edge[mu].other(nod) );
		}
	}
	Rez.pb(nod);
}

int main(){
	int m,a,b;
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	scanf("%d %d", &n, &m );
	for( i=1; i<=m; ++i ){
		scanf("%d %d", &a, &b );
		Vertex[a].pb(i);
		Vertex[b].pb(i);
		Edge[i]=edge(a,b,i);
	}
	for( i=1; i<=n; ++i ){
   		if( Vertex[i].size()&1 ){
			printf("-1\n");
			return 0;
		}
	}
	euler(1);
	for( i=Rez.size()-2; i>=0; --i )
		printf("%d ",Rez[i]);
	return 0;
}