Cod sursa(job #264054)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 21 februarie 2009 12:00:30
Problema Ciclu Eulerian Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 2.08 kb
#include<stdio.h>
#define infile "ciclueuler.in"
#define outfile "ciclueuler.out"
#define nmax 100*1001
#define mmax 1000*1001
struct stiva
	{
	int x; //nodul parcurgerii
	int ul; //pozitia ultimului fiu rezolvat
	} s[mmax]; //stiva in care vom face parcurgerea
struct lista
	{
	int n,p; //nodul si pozitia
	int pl; //pozitia din lista a arcului opus
	char v; //daca a fost vizitat sau nu
	} l[mmax]; //lista
struct nod
	{
	int p,g; //pozitia ultimului fiu din lista, si gradul sau
	} n[nmax]; //nodurile
int nr,mr; //numarul de noduri/muchii

//DFS - nerecursiv
void dfs(int x)
	{
	int ul,p=1; //capatul superior al stivei
	s[p].x=x; s[p].ul=n[x].p; //initializam stiva
	while(p) //cat timp avem elemente in stilva
		{
		for(ul=s[p].ul;ul;ul=l[ul].p) //parcurgem copii ramasi neparcursi
			if(!l[ul].v) //daca muchia nu a mai fost parcursa
				{
				l[l[ul].pl].v=l[ul].v=1; //marcam muchia ca vizitata (pe ambele sensuri)
				p++; s[p].x=l[ul].n; s[p].ul=n[s[p].x].p; //adaugam nodul in stiva
				s[p-1].ul=ul; //repunem pozitia
				break; //oprim pentru moment nodul curent
				}
		if(!ul) { if(p<1) printf("%d ",s[p].x); p--; } //inseamna k trebuie sa revenim o pozitie din stiva, deci afisem nodul
		}
	}

//adaugam muchie intre x si y, la pozitiile m, si m+1
void add(int m, int x , int y)
	{
	l[m].n=y; l[m].p=n[x].p; n[x].p=m; l[m].pl=++m; //adaugam arcul (x,y)
	l[m].n=x; l[m].p=n[y].p; n[y].p=m; l[m].pl=m-1; //adaugam arcul (y,x)
	n[x].g++; n[y].g++; //crestem gradele
	}

void citire()
	{
	int i,x,y;
	scanf("%d %d\n",&nr,&mr);
	for(i=1;i<=mr;i++)
		{
		scanf("%d %d\n",&x,&y); //citim muchia
		add(2*i-1,x,y); //adaugam muchia dintre x si y
		}
	}

void verificare()
	{
	int i;
	for(i=1;i<=nr;i++)
		if(n[i].g%2) //are grad impar
			break; //oprim
	if(i<=nr) printf("-1"); //inseamna ca nu poate forma un ciclu eulerian
	else dfs(1); //inseamna k se poate forma, deci facem parcurgerea dfs
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire();
verificare();

fclose(stdin);
fclose(stdout);
return 0;
}