Cod sursa(job #2399497)

Utilizator angelaAngela Visuian angela Data 7 aprilie 2019 17:12:31
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <unordered_set>
using namespace std;

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

using US  = unordered_multiset<int>;
using VUS = vector<US>;
using VI = vector<int>;

int n;
VUS G;
VI ciclu;

void citesteGraf();
void detCiclu(int x);
bool esteEulerian();

int main() {
	citesteGraf();
	if ( !esteEulerian() ) {
		fout << -1;
	} else {
		detCiclu(1);
		
		for (size_t i = 0; i < ciclu.size() - 1; ++i)
			fout << ciclu[i] << ' ';
	}
}

int x, y, m;

void detCiclu(int x) {
	while (!G[x].empty()) {
		auto it = G[x].begin(); y = *it;
		G[x].erase(it);    // sterg un y in G[x] (asta mai intai, ca sa nu invalidez iteratorul begin()
		it = G[y].find(x);
		if (it != G[y].end())
			G[y].erase(it); // sterg un x in G[y]	
		detCiclu(y);
	}
	ciclu.emplace_back(x);
}

bool esteEulerian() {
	for (auto ms : G)
		if (ms.size() & 1)
			return false;
	return true;
}

void citesteGraf() {
	fin >> n >> m;
	G = VUS(n + 1);
	while (m--) {
		fin >> x >> y;
		G[x].emplace(y);
		G[y].emplace(x); 
	}
}