Cod sursa(job #368262)

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

void erase(int i){
	if (rel[muchii[i].x]==muchii[i].qx) rel[muchii[i].x]=rel[muchii[i].x]->urm; else {
		muchii[i].qx->prev->urm=muchii[i].qx->urm;
		if (muchii[i].qx->urm) muchii[i].qx->urm->prev=muchii[i].qx->prev;
	}
	if (rel[muchii[i].y]==muchii[i].qy) rel[muchii[i].y]=rel[muchii[i].y]->urm; else {
		muchii[i].qy->prev->urm=muchii[i].qy->urm;
		if (muchii[i].qy->urm) muchii[i].qy->urm->prev=muchii[i].qy->prev;
	}
}

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;
		muchii[i].x=x;muchii[i].y=y;
		q=new list;q->link=i;q->nod=y;q->urm=rel[x];q->prev=0;if (rel[x]) rel[x]->prev=q;rel[x]=q;
		muchii[i].qx=q;
		q=new list;q->link=i;q->nod=x;q->urm=rel[y];q->prev=0;if (rel[y]) rel[y]->prev=q;rel[y]=q;
		muchii[i].qy=q;
		++st[x].nod;++st[y].nod;
	}
	fi.close();
	for (int i=1;i<=N;++i) if (st[i].nod%2) { ok=0;return ;}
}

void euler(){
	vf=1;
	st[vf].nod=1;
	st[vf].q=rel[1];
	while (vf){
		if (st[vf].q==NULL){
			if (vf>1) fo<<st[vf].nod<<" ";
			--vf;
		} else if (viz[st[vf].q->link]==0){
			viz[st[vf].q->link]=1;
			erase(st[vf].q->link);
			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();
	} else { fo<<"-1\n"; }
	fo.close();
	return 0;
}