Cod sursa(job #531945)

Utilizator skullLepadat Mihai-Alexandru skull Data 10 februarie 2011 17:24:03
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
#include <list>
using namespace std;
#define mx 500005
#define nmax 100005

list<int> Graf[nmax];
int sol[mx];
int N;

inline void euler(int nod)
{
	list<int>::iterator it,jt;
	int x;

	it=Graf[nod].begin();

	while(it!=Graf[nod].end())
	{
		x=*it;
		jt=Graf[*it].begin();
		while(jt!=Graf[*it].end())
		{
			if(*jt==nod)
			{
				Graf[*it].erase(jt);
				break;
			}
			jt++;
		}
		Graf[nod].pop_front();
		euler(x);
		it=Graf[nod].begin();
	}

	sol[++N]=nod;
}

int main()
{
    int n, m, x, y, i;
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);

	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		Graf[x].push_back(y);
		Graf[y].push_back(x);
	}

	for(i=1;i<=n;i++)
		if(Graf[i].size()%2)
		{
			printf("-1\n");
			return 0;
		}
	N = 0;
	euler(1);
	for(i = N;i > 1;i--)
		printf("%d ",sol[i]);
	return 0;
}