Cod sursa(job #396098)

Utilizator loginLogin Iustin Anca login Data 14 februarie 2010 15:30:36
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
# include <fstream>
using namespace std;
int n, m, *a[100003], e[500003], ne, gr[100003];

void add (int i, int j)
{
	a[i][0]++;
	a[i]=(int *)realloc (a[i], (a[i][0]+1)*4);
	a[i][a[i][0]]=j;
}

void read ()
{
	ifstream fin ("ciclueuler.in");
	fin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		a[i]=(int *)malloc (4);
		a[i][0]=0;
	}
	int x, y;
	for (int i=1;i<=m;i++)
	{
		fin>>x>>y;
		gr[x]++;
		gr[y]++;
		add(x, y);
		add(y, x);
	}
}

void sterge (int i, int j)
{
	int k;
	for (k=1;k<=a[a[i][j]][0] && a[a[i][j]][k]!=i;k++);
	a[a[i][j]][k]=a[a[i][j]][a[a[i][j]][0]];
	a[a[i][j]][0]--;		
	a[i][j]=a[i][a[i][0]];
	a[i][0]--;
}

void euler (int i)
{
	for (int j=1;j<=a[i][0];j++)
	{
		sterge (i, j);
		euler (a[i][j]);
	}
	e[++ne]=i;
}
ofstream fout ("ciclueuler.out");


int main ()
{
	read ();
	for (int i=1;i<=n;i++)
		if (gr[i]%2==1)
		{
			fout<<"-1";
			return 0;
		}
	euler (1);
	for (int i=2;i<=ne;i++)
		fout<<e[i]<<" ";
	return 0;
}