Cod sursa(job #1418346)

Utilizator OrolesVultur Oroles Data 12 aprilie 2015 20:17:56
Problema Ciclu Eulerian Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>

struct Nod
{
	std::list<int> vecini;
};

Nod nodes[100000];
int ciclu[100000];
int contorCiclu;
int N,M;

std::vector<int> stack;


void euler( int v )
{
	stack.push_back(v);
	while( !stack.empty() )
	{
		if ( !nodes[stack.back()].vecini.empty() )
		{
			int w = nodes[stack.back()].vecini.front();
			nodes[stack.back()].vecini.pop_front();
			stack.push_back( w );
		}
		else
		{
				int value = stack.back();
				stack.pop_back();
				ciclu[contorCiclu++] = value;
		}
	}
}

int main(int argc, char* argv[])
{
	std::ifstream input("ciclueuler.in");
	std::ofstream output("ciclueuler.out");

	input >> N >> M;
	for ( int i = 0; i < M; ++i )
	{
		int first, second;
		input >> first >> second;
		nodes[first].vecini.push_back( second );
	}

	euler(1);

	for ( int i = contorCiclu-1; i > 0; --i )
	{
		output << ciclu[i] << " ";
	}

	input.close();
	output.close();
	return 0;
}