Cod sursa(job #1492730)

Utilizator tain1234andrei laur tain1234 Data 28 septembrie 2015 02:47:42
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>
#include <map>
using namespace std;
vector<int> No[100001];
int gr[100001];
map<pair<int, int>,bool> del;
vector<int> cicle;
ifstream f("ciclueuler.in");
ofstream of("ciclueuler.out");
void euler(int root){
	stack<int> s;
	pair<int, int>p;
	s.push(root);
	while (!s.empty()){
		int x = s.top();
		while (No[x].size() > 0 && del[make_pair(x, No[x].back())] == 1){
			del[make_pair(x, No[x].back())] = 0;
			No[x].pop_back();
		}
		if (No[x].size() > 0){
			int c = No[x].back();
			No[x].pop_back();
			s.push(c);
			del[make_pair(c, x)] = 1;
			//No[c].erase(find(No[c].begin(), No[c].end(), x));
		}
		else{
			cicle.push_back(x);
			s.pop();
		}
	}
}
int main(){
	int N, M, a, b;
	string s;
	getline(f,s);
	int nr, j;
	nr = 0;
	j = 0;
	while (s[j] != ' '){
		nr = nr * 10 + s[j] - '0';
		++j;
	}
	N = nr;
	++j;
	nr = 0;
	while (j<s.size()){
		nr = nr * 10 + s[j] - '0';
		++j;
	}
	M = nr;
	for (int i = 0; i < M; ++i){
		getline(f, s);
		nr = 0;
		j = 0;
		while (s[j] !=' '){
			nr = nr * 10 + s[j]-'0';
			++j;
		}
		a = nr;
		++j;
		nr = 0;
		while (j<s.size()){
			nr = nr * 10 + s[j] - '0';
			++j;
		}
		b = nr;
		No[a].push_back(b);
		No[b].push_back(a);
		++gr[a]; ++gr[b];
		del[make_pair(a, b)] = 0;
		del[make_pair(b, a)] = 0;
	}
	for (int i = 1; i <= N; ++i)
	if (gr[i] % 2 == 1) {
		of << -1; return 0;
	}
	euler(1);
	for (int i = 0; i < cicle.size() - 1; ++i)
		of << cicle[i] << " ";
}