Cod sursa(job #971679)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 9 iulie 2013 21:57:15
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb

#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>

const int MAX_N(100001);

int n, m;
std::deque<int> Graph [MAX_N];
bool Ok;
bool Mark [MAX_N];
std::vector<int> Cycle;
std::stack<int> Stack;

inline void Read (void)
{
	std::freopen("ciclueuler.in","r",stdin);
	std::scanf("%d %d\n",&n,&m);
	for (int i(0), a, b ; i < m ; ++i)
	{
		std::scanf("%d %d",&a,&b);
		Graph[a].push_back(b);
		Graph[b].push_back(a);
	}
	std::fclose(stdin);
}

inline void Print (void)
{
	std::freopen("ciclueuler.out","w",stdout);
	if (Ok)
	{
		for (int index(0) ; index < Cycle.size() ; ++index)
			std::printf("%d ",Cycle[index]);
	}
	else
		std::printf("-1");
	std::putchar('\n');
	std::fclose(stdout);
}

inline void BreadthFirstSearch (void)
{
	std::queue<int> queue;
	queue.push(1);
	Mark[1] = true;
	int i, j;
	while (!queue.empty())
	{
		i = queue.front();
		queue.pop();
		for (j = 0 ; j < Graph[i].size() ; ++j)
			if (!Mark[Graph[i][j]])
			{
				Mark[Graph[i][j]] = true;
				queue.push(Graph[i][j]);
			}
	}
}

inline bool Valid (void)
{
	BreadthFirstSearch();
	for (int i(1) ; i <= n ; ++i)
		if (!Mark[i] || Graph[i].size() % 2)
		{
			Ok = false;
			return false;
		}
	Ok = true;
	return true;
}

inline void DepthFirstSearch (int node)
{
	int neighbor;
	while (!Graph[node].empty())
	{
		Stack.push(node);
		neighbor = Graph[node].front();
		Graph[node].pop_front();
		auto ptr(std::find(Graph[neighbor].begin(),Graph[neighbor].end(),node));
		Graph[neighbor].erase(ptr);
		node = neighbor;
	}
}

inline void EulerCycle (void)
{
	int node(1);
	do
	{
		DepthFirstSearch(node);
		node = Stack.top();
		Stack.pop();
		Cycle.push_back(node);
	}
	while (!Stack.empty());
}

int main (void)
{
	Read();
	if (Valid())
		EulerCycle();
	Print();
	return 0;
}