Cod sursa(job #672084)

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

const int MAXSIZE = 100001;

ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");

int nodes,edges;
vector<int> graph[MAXSIZE];
vector<int> solution;

void euler(int node);
bool hasEulerianCycle();

int main() {
	in >> nodes >> edges;

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

		graph[from].push_back(to);
		graph[to].push_back(from);
	}

	if(!hasEulerianCycle())
		out << "-1\n";
	else {
		euler(1);
		solution.pop_back();
		for(vector<int>::iterator it=solution.begin();it!=solution.end();++it)
			out << *it << " ";
		out << "\n";
	}

	return (0);
}

inline void euler(int node) {
	while(!graph[node].empty()) {
		int nextNode = *graph[node].begin();

		for(vector<int>::iterator it=graph[nextNode].begin();it!=graph[nextNode].end();++it)
			if(*it == node) {
				graph[nextNode].erase(it);
				break;
			}

		graph[node].erase(graph[node].begin());

		euler(nextNode);
	}

	solution.push_back(node);
}

bool hasEulerianCycle() {
	for(int i=1;i<=nodes;i++)
		if((graph[i].size() %2))
			return false;
	return true;
}