Cod sursa(job #647869)

Utilizator Tucu94Andrei Tuculanu Tucu94 Data 12 decembrie 2011 08:24:05
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
using namespace std;
ifstream f("ciclueuler.in");
ofstream fout("ciclueuler.out");
struct  nod{
	int inf;
	nod* adr;
}*v[100001];
int n,m,sf,V,E[100001],j,i,ok;
void citire()
{
	int g[100001];
	f>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		f>>x>>y;
		g[x]++;
		g[y]++;
		nod *p=new nod;
		p->inf=y;
		p->adr=v[x];
		v[x]=p;
		p=new nod;
		p->inf=x;
		p->adr=v[y];
		v[y]=p;
	}
	for(int i=1;i<=n;i++)
		if(g[i]%2!=0){
			fout<<-1;
				ok=1;
		}
}
void euler(int I)
{
	for(nod*p=v[E[I]];p;p=p->adr)
	{
		V=p->inf;
		v[E[I]]=p->adr;
		if(v[V]->inf==E[I])v[V]=v[V]->adr;
		else
		for(nod *q=v[V];q->adr;q=q->adr)
			if(q->adr->inf==E[I])
			{
				q->adr=q->adr->adr;
				break;
			}
			break;
	}
		sf++;
		for(j=sf;j>I;j--)
			E[j]=E[j-1];
		E[++I]=V;
		if(E[I]==1&&v[E[I]]==0)
			return;
		else
			euler(I);
		
	
}
main()
{
	citire();
	if(ok==1)
		return 0;
	E[1]=1;
	euler(1);
	for(i=1;i<=sf;i++)
		fout<<E[i]<<" ";
	return 0;
}