Cod sursa(job #420778)

Utilizator NemultumituMatei Ionita Nemultumitu Data 20 martie 2010 15:51:55
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>
using namespace std;
int n,m,cnt=0;
vector <pair<int,int> > v[100100];
int grad[100100],ciclu[500100],gr[100100];

void citire()
{
	scanf("%d%d",&n,&m);
	int x,y;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		if (x!=y)
		{
			v[x].push_back(make_pair(y,v[y].size()));
			v[y].push_back(make_pair(x,v[x].size()-1));
			++grad[x];
			++grad[y];
			++gr[x];
			++gr[y];
		}
		else
		{
			v[x].push_back(make_pair(x,v[x].size()));
			++grad[x];
			gr[x]+=2;
		}
	}
}

void euler(int nod)
{
	for (int i=0;i<v[nod].size();++i)
		if (v[nod][i].first)
		{
			grad[nod]--;
			int aux=v[nod][i].first;
			if (aux!=nod)
				grad[aux]--;
			v[nod][i].first=0;
			v[aux][v[nod][i].second].first=0;
			euler(aux);
		}
	if (!ciclu[m])
		ciclu[++cnt]=nod;
}

int main()
{
	freopen ("ciclueuler.in","r",stdin);
	freopen ("ciclueuler.out","w",stdout);
	citire();
	bool k=0;
	for (int i=1;i<=n;++i)
		if (gr[i]&1)
			k=1;
	if (k)
	{
		printf("%d",-1);
		return 0;
	}
	int i=1;
	while (!grad[i])
		++i;
	euler(i);
	if (!ciclu[m])
	{
		printf("%d",-1);
		return 0;
	}
	for (int i=1;ciclu[i];++i)
		printf("%d ",ciclu[i]);
	return 0;
}