Cod sursa(job #728740)

Utilizator gabriel93Robu Gabriel gabriel93 Data 28 martie 2012 22:21:58
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<stdio.h>
#include<list>
#include<stack>
#define Nmax 100100
using namespace std;
int n,m;

list <int> g[Nmax];
stack <int> st;
int nr[Nmax];

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

void sterg(int x,int y)
{
	list<int>::iterator it;
	g[x].pop_front();
	for(it=g[y].begin();it!=g[y].end();++it)
		if(*it==x)
		{
			g[y].erase(it);
			break;
		}
}

void eulerian(int nod)
{
	int x;
	while(!g[nod].empty())
	{
		x=g[nod].front();
		st.push(x);
		sterg(nod,x);
		nod=x;
	}
}

void rezolv()
{
	int x;
	x=1;
	do
	{
		eulerian(x);
		x=st.top();
		st.pop();
		printf("%d ",x);
	}while(!st.empty());
}

int main()
{
	int i,ok;
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	citire();
	ok=1;
	for(i=1;i<=n;++i)
		if(nr[i]&1)
		{
			ok=0;
			printf("-1");
			break;
		}
	if(ok)
		rezolv();
	fclose(stdin);
	fclose(stdout);
	return 0;
}