Cod sursa(job #697932)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 29 februarie 2012 11:40:07
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int dimn = 100005, dimm = 500005;
int N, M, g[dimn], viz[dimm], R[dimm], S[dimm];
vector < pair <int, int> > V[dimn];

void cit ()
{
	fi >> N >> M;
	for (int i = 1, x, y; i <= M; i++)
	{
		fi >> x >> y;
		V[x].push_back (make_pair (y, i));
		V[y].push_back (make_pair (x, i));
		g[x]++, g[y]++;
	}
}

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; i++)
		if (!viz[i])
			return 0;
	return 1;
}

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

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

int main ()
{
	cit ();
	if (!verif1 ())
	{
		fo << "-1 ";
		return 0;
	}
	euler ();
	if (!verif2 ())
	{
		fo << "-1 ";
		return 0;
	}
	afi ();
	return 0;
}