Cod sursa(job #544044)

Utilizator avram_florinavram florin constantin avram_florin Data 28 februarie 2011 22:27:51
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<stdio.h>
#include<list>
using namespace std;
#define mx 500005
#define nmax 100005

list <int> Graf[100001];
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;
}