Cod sursa(job #368247)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 24 noiembrie 2009 11:54:40
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");
int viz[500010];
struct list{
	int nod,link;
	list *urm;
} *rel[100010];
int rez[500010],vf,N,M,nr;
struct stiva{
	int nod;
	list *q;
} st[500010];
int grad[100010];
int ok=1;

void citire(){
	fi>>N>>M;
	int x,y;
	list *q;
	memset(rel,0,sizeof(rel));
	for (int i=1;i<=M;++i){
		fi>>x>>y;
		q=new list;q->link=i;q->nod=y;q->urm=rel[x];rel[x]=q;
		q=new list;q->link=i;q->nod=x;q->urm=rel[y];rel[y]=q;
		++grad[x];++grad[y];
	}
	fi.close();
	for (int i=1;i<=N;++i) if (grad[i]%2) { ok=0;return ;}
}

void euler(){
	vf=1;
	st[vf].nod=1;
	st[vf].q=rel[1];
	while (vf){
		if (st[vf].q==NULL){
			rez[++nr]=st[vf].nod;
			--vf;
		} else if (viz[st[vf].q->link]==0){
			viz[st[vf].q->link]=1;
			rel[st[vf].nod]=st[vf].q->urm;
			st[vf+1].nod=st[vf].q->nod;
			st[vf+1].q=rel[st[vf+1].nod];
			++vf;
		} else st[vf].q=st[vf].q->urm;
	}
}


int main(){
	citire();
	nr=0;
	if (ok){ 
	euler();
	for (int i=2;i<nr;++i) fo<<rez[i]<<" ";
	fo<<rez[nr]<<"\n";} else { fo<<"-1\n"; }
	fo.close();
	return 0;
}