Cod sursa(job #432196)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 1 aprilie 2010 22:42:11
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<stdio.h>
#include<vector>
#define nmax 100002
#define mmax 600005

using namespace std;

vector<int> g[nmax];
vector<int>::iterator it;
int grad[nmax],n,m,i,j,k,x,y, stiva[mmax], nod, rez[mmax], nr, aux;

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);
		g[x].push_back(y);
		g[y].push_back(x);
		grad[x]++;
		grad[y]++;
	}
	for(i=1;i<=n;i++)
		if(grad[i]%2==1)
		{
			printf("-1\n");
			return ;
		}

	stiva[++k]=1;
	for(;k>0;)
	{
		nod=stiva[k];
		if(!grad[nod])
		{
			rez[++nr]=nod;
			k--;
			continue;
		}
		aux=g[nod].back();
		g[nod].pop_back();
		grad[nod]--;
		grad[aux]--;
		stiva[++k]=aux;
		for(it=g[aux].begin();it!=g[aux].end();++it)
			if(*it==nod)
			{
				g[aux].erase(it);
				break;
			}
	}
	for(i=nr;i>=1;i--)
		printf("%d ", rez[i]);
	return 0;
}