Cod sursa(job #728923)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 29 martie 2012 09:30:25
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
using namespace std;

ifstream f("ciclueuler.in"); ofstream g("ciclueuler.out");

struct muchie {int n; muchie *a;};

muchie *v[100005];
int r[500005];
int par[100005];
int rn, i, j, n, m, x, y, aux;
muchie *p;
bool kay;

void dfs (int fx){
	muchie *fq=v[fx];
	
	while (fq!=NULL){
		if (fq->n!=0){
			aux=fq->n;
				
			fq->n=0;			
			p=v[aux];
			while (p->n!=fx) p=p->a;
			p->n=0; 
			
			dfs(aux);
			r[++rn]=fx;
		}
		

		
		fq=fq->a;
	}
}

int main(){
	f>>n>>m;
	for (i=1; i<=m; i++){
		f>>x>>y;
		p=new muchie; p->n=y; p->a=v[x]; v[x]=p;
		p=new muchie; p->n=x; p->a=v[y]; v[y]=p;
		par[x]++; par[y]++;
	}
	
	kay=1;
	for (i=1; i<=n; i++) if (par[i]%2==1){ kay=0; break;}
	
	if (kay==0) g<<-1;
	else {
		dfs(1);
		for (i=1; i<=rn; i++) g<<r[i]<<" ";
	}
}