Cod sursa(job #418709)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 16 martie 2010 11:53:56
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<cstdio>
#include<iostream>
using namespace std;
struct nod
{
	int info;
	nod *next;
};
#define nn 100005
nod *g[nn];
int e[nn],n,m,grad[nn],v[nn];
void adauga(int a,int b)
{
	nod *p=new nod;
	p->info=b;
	p->next=g[a];
	g[a]=p;
}
void sterg(int k,int kk)
{
	--grad[k];
	--grad[kk];
	int pp=1;
	for(nod *p=g[k],*q=p->next;p&&q&&pp;)
		if(q->info==kk)
		{
			p->next=q->next;
			delete q;
			q=p->next;
			pp=0;
		}
		else
			p=p->next,q=q->next;
	if(g[k]->info==kk)
	{
		nod *p=g[k];
		g[k]=g[k]->next;
		delete p;
	}
}
void euler(int k)
{
	while(g[k])
	{
		int kk=g[k]->info;
		sterg(k,kk);
		euler(kk);
	}
	e[++m]=k;
}
void bfs()
{
	int coada[nn],st,dr;
	coada[1]=1;
	st=dr=1;
	v[1]=1;
	while(st<=dr)
	{
		for(nod *p=g[coada[st]];p;p=p->next)
			if(!v[p->info])
			{
				v[p->info]=1;
				coada[++dr]=p->info;
			}
		++st;	
	}
}
int posibil()
{
	bfs();
	int pp=1;
	for(int i=1;i<=n&&pp;++i)
		if(!v[i]||grad[i]%2)
			pp=0;
	if(!pp)return 0;
	return 1;
}
int main()
{
	int a,b;
	freopen("ciclueuler.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(;m;--m)
	{
		scanf("%d%d",&a,&b);
		adauga(a,b);
		++grad[a];
	}
	if(posibil())
		euler(1);
	freopen("ciclueuler.out","w",stdout);
	if(m)
		for(int i=1;i<=m;++i)
			printf("%d ",e[i]);
	else
		printf("-1");
	return 0;
}