Cod sursa(job #672369)

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

const int MAXSIZE = 100001;

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

int nodes,edges;
vector<int> graph[MAXSIZE];
stack<int> stk;
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);
}

void euler(int startNode) {
	stk.push(startNode);

	while(!stk.empty()) {
		int node = stk.top();

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

			graph[nextNode].erase(find(graph[nextNode].begin(),graph[nextNode].end(),node));
			graph[node].erase(graph[node].begin());

			stk.push(nextNode);

			node = nextNode;
		}

		solution.push_back(stk.top());

		stk.pop();
	}
}

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