Cod sursa(job #755396)

Utilizator rzvrzvNicolescu Razvan rzvrzv Data 5 iunie 2012 16:32:55
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<cstdio>
#include<vector>
#include<deque>

using namespace std;

vector<int>::iterator it;
vector<int>L[100001];
deque<int>q;
int n,i,m,x,y;


void euler(int x,int y)
{
	if(y!=0)
	{
		q.push_front(x);
		for (it=L[y].begin();it!=L[y].end();++it)
		{
			if (*it==x)
			{
				L[y].erase(it);
				break;
			}
		}
		q.push_front(y);
	if (L[x].size()>0)
	{
		L[x].pop_back();
		euler(y,L[x].front());
	}
	else return;
	}
	else if (L[x].size()>0)
	{
		L[x].pop_back();
		euler(L[x].front(),x);
	}
	else return;
}

int main()
{
	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);	
		L[x].push_back(y);
		L[y].push_back(x);
	}
	for (i=1;i<=n;i++)
	{
		if (L[x].size()%2==1)
		{
			printf("-1\n");
			return 0;
		}
	}
	euler(1,0);
	for (i=0;i<q.size();i++)
	{
		printf("%d ",q[i]);
	}
	printf("\n");
	return 0;
}