Cod sursa(job #543775)

Utilizator avram_florinavram florin constantin avram_florin Data 28 februarie 2011 16:27:07
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<cstdio>
#include<list>
#define MaxN 100001
#define MaxM 500001

using namespace std;

int n,m,ind,sol[MaxM];
list<int>G[MaxN];

void euler(int nod)
{
	list<int>::iterator it,jt;
	int x;
	it = G[nod].begin();
	while( it != G[nod].end() )
		{
			x = *it;
			jt = G[*it].begin();
			while( jt != G[*it].end() )
				{
					if( *jt == nod )
						{
							G[*it].erase(jt);
							break;
						}
					jt++;
				}
			G[nod].pop_front();
			euler(x);
			it = G[nod].begin();
		}
	sol[++ind] = nod;
}

int main()
{
	freopen("ciclueuler.in" , "r" , stdin );
	freopen("ciclueuler.out" , "w" , stdout);
	scanf("%d%d" , &n,&m);
	int i,x,y;
	for( i = 1 ; i <= n ; i++ )
		{
			scanf("%d%d" , &x,&y);
			G[x].push_back(y);
			G[y].push_back(x);
		}
	for( i = 1 ; i <= n ; i++ )
		if( G[i].size() % 2 )
			{
				printf("-1\n");
				return 0;
			}
	euler(1);
	sol[1] = sol[ind];
	for( i = ind ; i ; i-- )
		printf("%d " , sol[i]);
	return 0;
}