Cod sursa(job #2427995)

Utilizator eduardandrei20Nechifor Eduard Andrei eduardandrei20 Data 3 iunie 2019 11:59:26
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <stack>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

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

struct muchie {
	int nrMuchie, nod;
};

vector<int>ciclu;
const int dim = 100001;
int grade[dim];
int noduri, muchii;
vector<muchie>G[dim];
stack<int>s;
int sters[500001];

void input() {
	int c = 0;
	in >> noduri >> muchii;
	for (int p = 0; p < muchii; p++) {
		int i, j;
		in >> i >> j;
		++c;
		grade[i]++, grade[j]++;
		muchie x;
		x.nod = j;
		x.nrMuchie = c;
		G[i].push_back(x);
		x.nod = i;
		G[j].push_back(x);
	}
	return;
}

void euler() {
	s.push(1);
	while (s.empty() == false) {
		int nod = s.top();
		if (G[nod].size()) {
			int nrM = G[nod].back().nrMuchie;
			int node = G[nod].back().nod;
			G[nod].pop_back();
			if (!sters[nrM]) {
				sters[nrM] = true;
				s.push(node);
			}
		}
		else {
			ciclu.push_back(nod);
			s.pop();
		}
	}
	return;
}

int main() {

	input();
	for (int i = 1; i <= noduri; i++) {
		if (grade[i] & 1) {
			out << "-1";
			return 0;
		}
	}
	euler();
	int x = ciclu.size();
	for (int i = 0; i < x - 1; i++) {
		out << ciclu[i] << " ";
	}

	return 0;
}