Cod sursa(job #544040)

Utilizator avram_florinavram florin constantin avram_florin Data 28 februarie 2011 22:21:21
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<cstdio>
#include<list>

using namespace std;

int n,m;
list <int> Graf[100001];
list <int> Q;

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();
		}
	Q.push_back(nod);
}

int main()
{
	int x,y,i;
	freopen("euler.in" , "r" , stdin);
	freopen("euler.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() & 1 )
			{
				printf("-1\n");
				return 0;
			}
	euler(1);
	Q.pop_back();
	list<int>::iterator it;
	for( it = Q.begin() ; it != Q.end() ; ++it )
		printf("%d " , *it );
	return 0;
}