Cod sursa(job #1064982)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 22 decembrie 2013 16:09:50
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <fstream>
#include <list>
#include <queue>
#include <stack>

class Graph {

public:
		
	struct Vertex {
		std::list<int> myL;
		Vertex() : myL(std::list<int>()) {
		}
	};
	
	int nV;
	
	Vertex *myArr;
	
	~Graph() {
		nV = 0;
		delete[] myArr; 
	}
	
	Graph(int a) : nV(a) {
		myArr = new Vertex[nV + 1];
		for(int i = 1; i <= nV; i++) {
			myArr[i] = Vertex();
		}
	}
	
	bool eulerian() {
		for(int i = 1; i <= nV; i++) {
			if((int)myArr[i].myL.size() & 1) {
				return false;
			}
		}
		std::queue<int> myQ;
		char *myB = new char[nV + 1];
		for(int i = 1; i <= nV; i++) {
			myB[i] = 0;
		}
		myQ.push(1);
		myB[1] = 1;
		while(!myQ.empty()) {
			int i = myQ.front();
			myQ.pop();
			for(auto it = myArr[i].myL.begin(); it != myArr[i].myL.end(); it++) {
				if(myB[*it] == 0) {
					myQ.push(*it);
					myB[*it] = 1;
				}
			}
		}
		bool ok = true;
		for(int i = 1; i <= nV; i++) {
			if(myB[i] == 0) {
				ok = false;
				break;
			}
		}
		delete[] myB;
		return ok;
	}
	
	void pushEdge(int a, int b) {
		myArr[a].myL.push_back(b);
		myArr[b].myL.push_back(a);
	}
	
	std::list<int> solve() {
		std::list<int> sol;
		std::stack<int> myS;
		int x = 1;
		do{
			while(!myArr[x].myL.empty()) {
				int y = myArr[x].myL.front();
				myArr[x].myL.pop_front();
				myS.push(x);
				std::list<int>::iterator it;
				for(auto it = myArr[y].myL.begin(); it != myArr[y].myL.end(); it++) {
					if(*it == x) {
						myArr[y].myL.erase(it);
						break;
					}
				}
				x = y;
			}
			x = myS.top();
			myS.pop();
			sol.push_back(x);
		}while(!myS.empty());
		return sol;
	}
};

int main() {
	std::ifstream in("ciclueuler.in");
	std::ofstream out("ciclueuler.out");
	int nV, nE;
	in >> nV >> nE;
	Graph a(nV);
	for(int i = 0; i < nE; i++) {
		int c, d;
		in >> c >> d;
		a.pushEdge(c, d);
	}
	if(!a.eulerian()) {
		out << -1;
		return 0;
	}
	std::list<int> mySol = a.solve();
	for(auto it = mySol.begin(); it != mySol.end(); it++) {
		out << *it << ' ';
	}
	return 0;
}