Cod sursa(job #271614)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 5 martie 2009 17:18:59
Problema Ciclu Eulerian Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define FIN "ciclueuler.in"
#define FOUT "ciclueuler.out"
#define N 100010 
#define M 50010
using namespace std;

int n,m,nr,ok;
int * a[N];
int c[N], *poz[N];

void read()
{
	int g[N]={0};
	pair <int,int> v[M];
	freopen(FIN, "r", stdin);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d %d", &v[i].first, &v[i].second);
		++g[v[i].first];
		++g[v[i].second];
	}
	for (int i = 1; i <= n; ++i)
	{
		a[i] = new int[1+g[i]];
		a[i][0] = 0;
		poz[i] = new int[1+g[i]];
		poz[i][0] = 0;
		if (g[i] % 2)
		{
			printf("-1\n");
			exit(0);
		}
	}
	
	for (int i = 1; i <= m; ++i)
	{
		if(v[i].first == v[i].second)
		{
			a[ v[i].first ][ ++a[v[i].first][0]] = v[i].second;
			poz[ v[i].first ][ ++poz[v[i].first][0]] = a[v[i].first][0];
			continue;
		}
		a[ v[i].first ][ ++a[v[i].first ][0]] = v[i].second;
		poz[ v[i].first ][ ++poz[v[i].first][0] ] =  a[v[i].second][0] + 1; 
		
		a[ v[i].second ][ ++a[v[i].second ][0]] = v[i].first;
		poz[ v[i].second ][ ++poz[v[i].second][0]] = a[v[i].first][0];
	}
	
}

void solve(int x)
{
	int i,y;
	for (i = 1; i <= a[x][0]; ++i)
	{
		y = a[x][i];
		if (y == -1)
			continue;
		a[x][i] = -1;
		if(y!=x)
			a[y][ poz[x][i] ] = -1;
		solve(y);
	}
	c[ ++nr] = x;
}

void write()
{
	freopen(FOUT, "w", stdout);
	if (ok)
	{
		printf("-1\n");
		return;
	}
	for (int i = 1; i < nr-1; ++i)
		printf("%d ", c[i]);
	printf("%d\n", c[nr-1]);
}

void write2()
{
	freopen(FOUT, "w", stdout);
	printf("a :\n");
	for (int i = 1; i <= n; ++i)
	{
		printf("%d :   ", i);
		for (int j = 1; j <= a[i][0]; ++j)
			printf("%d ", a[i][j]);
		printf("\n");
	}
	printf("poz :\n");
	for (int i = 1; i <= n; ++i)
	{
		printf("%d :   ", i);
		for (int j = 1; j <= poz[i][0]; ++j)
			printf("%d ", poz[i][j]);
		printf("\n");
	}
	fclose(stdout);
}

int main()
{
	read();
	//write2();
	solve(1);
	write();
}