Cod sursa(job #849558)

Utilizator SteveStefan Eniceicu Steve Data 7 ianuarie 2013 11:42:48
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

#define TR( C, it ) for( typeof(C.begin()) it = C.begin(); it != C.end(); it++ )
int N, M;
vector <int> muchii[500011];
int visited[100011];
stack <int> stiva;
vector <int> Answer;

void Citire ()
{
	ifstream fin ("ciclueuler.in");
	fin >> N >> M;
	for (int i = 0, a, b; i < M; i++)
	{
		fin >> a >> b;
		muchii[a].push_back (b);
		muchii[b].push_back (a);
	}
	fin.close ();
}

void DFS (int nod)
{
	visited[nod] = 1;
	for (int i = muchii[nod].size () - 1; i >= 0; i--)
		if (!visited[muchii[nod][i]]) DFS (muchii[nod][i]);
}

int Eulerian ()
{
	DFS (1);
	for (int i = 1; i <= N; i++)
		if ((!muchii[i].empty () && !visited[i]) || (muchii[i].size () % 2)) return 0;
	return 1;
}

void Sterge (int v, int u)
{
	muchii[v].pop_back ();
	TR (muchii[u], it)
	{
		if (*it == v)
		{
			muchii[u].erase (it);
			break;
		}
	}
}

void Euler (int nod)
{
	while (1)
	{
		if (muchii[nod].empty ()) return;
		int w = muchii[nod].back ();
		Sterge (nod, w);
		stiva.push (nod);
		nod = w;
	}
}

void Business ()
{
	int nod = 1;
	do
	{
		Euler (nod);
		nod = stiva.top ();
		stiva.pop ();
		Answer.push_back (nod);
	} while (!stiva.empty ());
}

void Scriere ()
{
	ofstream fout ("ciclueuler.out");
	if (!Eulerian ())
	{
		fout << "-1";
		fout.close ();
		return;
	}
	while (!Answer.empty ())
	{
		fout << Answer.back () << " ";
		Answer.pop_back ();
	}
	fout.close ();
}

int main ()
{
	Citire ();
	Business ();
	Scriere ();
	return 0;
}