Cod sursa(job #694888)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 28 februarie 2012 08:48:34
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 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, A[dimn], g[dimn], viz[dimm], R[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)
{
	for (int i = 0, f, m; i < V[n].size(); i++)
	{
		f = V[n][i].first;
		m = V[n][i].second;
		if (viz[m] == 0)
		{
			viz[m] = 1;
			euler (f);			
		}
	}
	R[++R[0]] = n;
}

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

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