Cod sursa(job #320151)

Utilizator swift90Ionut Bogdanescu swift90 Data 3 iunie 2009 18:41:52
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<stdio.h>
#include<vector>
using namespace std;
#define fs first
#define sc second
int n,m,cnt,poz;
typedef pair <int,int> hh;
vector <bool> fol(500010);
vector <hh> nr[100010];
vector <bool> viz(100100);
int s[100100],afis[500100];
void df(int x){
	if(viz[x])
		return;
	viz[x]=1;
	--cnt;
	for(int i=0;i<s[x];++i)
		df(nr[x][i].fs);
}
void euler(int x){
	for(int i=0;i<s[x];++i){
		if(!fol[ nr[x][i].sc ]){
			fol[ nr[x][i].sc ]=1;
			euler(nr[x][i].fs);
		}
	}
	afis[++poz]=x;
}
int main(){
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	int i,x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		nr[x].push_back( hh(y,i) );
		nr[y].push_back( hh(x,i) );
		++s[x];
		++s[y];
	}
	for(i=1;i<=n;++i){
		if(s[i]%2){
			printf("-1\n");
			fclose(stdin);
			fclose(stdout);
			return 0;
		}
	}
	
	cnt=n;
	df(1);
	if(cnt){
		printf("-1\n");
		fclose(stdin);
		fclose(stdout);
		return 0;
	}
	euler(1);
	for(i=1;i<poz;++i)
		printf("%d ",afis[i]);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}