Cod sursa(job #1080782)

Utilizator roby2001Sirius roby2001 Data 12 ianuarie 2014 21:50:17
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
/*
          ~Keep It Simple!~
*/
  
#include <stdio.h>
#include <list>
#include <stack>

using namespace std;

int N,M,C[100006];

bool viz[100005];

list<int> G[100005],S,R;

int IsEuler(int node)
{

	S.push_back(node);

	for(list<int>::iterator it = S.begin(); it!=S.end(); it++)
	{

		node = *it;

		viz[node] = 1;

		for(list<int>::iterator j = G[node].begin(); j!=G[node].end(); j++)
			if(!viz[*j])
			{
			    S.push_back(*j);
				viz[*j] = 2;
			}
	}
	for(int i=1; i<=N; i++)
		if( !viz[i] || G[i].size()%2 )
			return 0;
	return 1;
}

void DeleteRoad(int a,int b)
{
	G[a].pop_front();

	for(list<int>::iterator it=G[b].begin(); it!=G[b].end(); it++)
		if(*it==a)
		{
			G[b].erase(it);
			break;
		}
}

void ComputeEuler(int node)
{
	int nr=0;
	S.clear();
	do
	{

	while(true)
	{
		if( G[node].empty() )
			break;

		int x = G[node].front();

		S.push_back(node);

		DeleteRoad(node,x);

		node = x;
	}
	   node = S.back();
	   S.pop_back();
	   R.push_front(node);
	} while( !S.empty() );
	
	for(list<int>::iterator it = R.begin(); it!=R.end(); it++)
		printf("%d ",*it);
}

int main()
{
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);

	scanf("%d%d",&N,&M);

	int x,y;

	for(int i=1; i<=M; i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}

	if(IsEuler(1))
	{
		ComputeEuler(1);
	}
	else
		printf("-1");


}