Cod sursa(job #672088)

Utilizator feelshiftFeelshift feelshift Data 1 februarie 2012 16:24:29
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
// http://infoarena.ro/problema/ciclueuler
#include <fstream>
#include <vector>
using namespace std;

#define maxSize 100002

int nodes;
vector<int> graph[maxSize];
vector<int> nodeList;

void read();
bool eulerianCycle();
inline void euler(int currentNode);
void write(bool status);

int main() {
	read();

	if(eulerianCycle()) {
		euler(1);
		write(true);
	}
	else
		write(false);

	return (0);
}

void read() {
	ifstream in("ciclueuler.in");
	int edges,from,to;

	in >> nodes >> edges;
	for(int i=1;i<=edges;i++) {
		in >> from >> to;

		// graf neorientat
		graph[from].push_back(to);
		graph[to].push_back(from);
	}

	in.close();
}

// un multigraf este Eulerian (admite un ciclu Eulerian) daca si numai daca este conex si toate nodurile sale au grad par
bool eulerianCycle() {
	for(int currentNode=1;currentNode<=nodes;currentNode++)
		if(graph[currentNode].size() % 2)
			return false;

	return true;
}

inline void euler(int currentNode) {
	int next;
	vector<int>::iterator neighbour;
	vector<int>::iterator neighbourOfNeighbour;

	neighbour = graph[currentNode].begin();

	while(graph[currentNode].size()) {
		neighbour = graph[currentNode].begin();
		next = *neighbour;

		for(neighbourOfNeighbour=graph[next].begin();neighbourOfNeighbour!=graph[next].end();neighbourOfNeighbour++)
			if(*neighbourOfNeighbour == currentNode) {
				graph[next].erase(neighbourOfNeighbour);
				break;
			}

		// un fel de "graph[currentNode].pop_front();"
		// cu liste primesc Killed by signal 11(SIGSEGV) si Killed by signal 6(SIGABRT)
		neighbour = graph[currentNode].begin();
		graph[currentNode].erase(neighbour);

		euler(next);
	}

	nodeList.push_back(currentNode);
}

void write(bool status) {
	ofstream out("ciclueuler.out");
	vector<int>::iterator currentNode;

	// nodul de inceput apare de doua ori
	// (la inceput si la sfarsit)
	nodeList.pop_back();


	if(status)
		for(currentNode=nodeList.begin();currentNode!=nodeList.end();currentNode++)
			out << *currentNode << " ";
	else
		out << "-1";

	out.close();
}