Cod sursa(job #867739)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 30 ianuarie 2013 00:35:46
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define nmax 100100
using namespace std;

stack <int> St;
vector <int> G[nmax],Answer;
int N;

void EraseEdge(int Nod,int Vecin) {
	
	G[Nod][0]=G[Nod][G[Nod].size()-1];
	G[Nod].pop_back();
	G[Vecin].erase(find(G[Vecin].begin(),G[Vecin].end(),Nod));
	
}
void Solve() {
	
	int Nod;
	
	for(int i=1;i<=N;i++)
		if(G[i].size()&1)
			return;
		
	St.push(1);
	
	while(!St.empty()) {
		
		Nod=St.top();
		
		if(G[Nod].size()) {
			St.push(G[Nod].front());
			EraseEdge(Nod,G[Nod].front());
			}
		else {
			Answer.push_back(St.top());
			St.pop();
			}
		
		}
	
}
void Read() {
	
	int i,x,y,M;
	ifstream in("ciclueuler.in");
	in>>N>>M;
	
	while(M--) {
		
		in>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
		
		}
	
	in.close();
	
}
void Write() {
	
	ofstream out("ciclueuler.out");
	if(Answer.empty())
		out<<"-1\n";
	else {
		for(int i=1;i<Answer.size();i++)
			out<<Answer[i]<<' ';
		out<<'\n';
		}
	out.close();
	
}
int main() {
	
	Read();
	Solve();
	Write();
	
	return 0;
	
}