Cod sursa(job #629666)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 3 noiembrie 2011 18:41:06
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector> 

using namespace std;

const int N=100001;
const int M=500001;

int grad[N],n,m,stiva[M],varf,ciclu[M],sizeciclu;
vector <int> muchie[N];

void citire(){
	int i,x,y;
	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);
		muchie[x].push_back(y);
		muchie[y].push_back(x);
		grad[x]++;
		grad[y]++;
	}
}

void rezolvare(){
	int nod,i,j,fiu;
	varf=1;
	stiva[varf]=1;
	while(varf!=0){
		nod=stiva[varf];
		if(grad[nod]==0){
			ciclu[++sizeciclu]=nod;
			varf--;
			continue;
		}
		for(i=0;i<muchie[nod].size();++i){
			if(muchie[nod][i]!=-1){
				fiu=muchie[nod][i];
				muchie[nod][i]=-1;
				break;
			}
		}
		grad[nod]--;
		grad[fiu]--;
		for(i=0;i<muchie[fiu].size();++i){
			if(muchie[fiu][i]==nod){
				muchie[fiu][i]=-1;
				break;
			}
		}
		stiva[++varf]=fiu;	
	}
	for(i=1;i<=n;i++){
		if(grad[i]){
			printf("-1");
			return;
		}
	}
	for(i=1;i<sizeciclu;i++){
		printf("%d ",ciclu[i]);
	}
}

int main(){
	int i;
	citire();
	for(i=1;i<=n;++i){
		if(grad[i]%2){
			printf("-1");
			return 0;
		}
	}
	rezolvare();
	return 0;
}