Cod sursa(job #651720)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 21 decembrie 2011 10:57:51
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream fi ("ciclueuler.in");
ofstream fo ("ciclueuler.out");

const int dim = 100005;
int N, M[dim*5], R[dim*5], S[dim*5], g[dim];
struct vec { int v, m; };
vector <vec> V[dim];

void cit ()
{
	vec a;	
	fi >> N >> M[0];
	for (int i = 1, x, y; i <= M[0]; i++)
	{
		fi >> x >> y;
		a.m = i;
		a.v = y;
		V[x].push_back (a);
		a.v = x;
		V[y].push_back (a);
	}
}

int verif1 ()
{
	for (int i = 1; i <= N; i++)
	{
		if (g[i] & 1)
			return 0;
	}
	return 1;
}

int verif2 ()
{
	for (int i = 1; i <= M[0]; i++)
		if (M[i] == 0)
			return 0;
	return 1;
}

void euler ()
{
	int n, v, m;
	S[++S[0]] = 1;
	while (S[0] > 0)
	{
		n = S[S[0]];
		if (V[n].empty ())
		{
			R[++R[0]] = S[S[0]--]; 
			continue;
		}
		
		v = V[n].back().v;
		m = V[n].back().m;
		V[n].pop_back ();
		if (M[m] == 0)
		{
			S[++S[0]] = v;
			M[m] = 1;
		}
	}	
}

void afida ()
{
	for (int i = 1; i < R[0]; i++)
		fo << R[i] << '\n';	
}

void afinu ()
{
	fo << "-1\n";
}

int main ()
{
	cit ();
	if (verif1 ())
	{
		euler ();
		if (verif2 ())
			afida ();
		else
			afinu ();
	}
	else
		afinu ();
	
	return 0;
}