Cod sursa(job #2427797)

Utilizator eduardandrei20Nechifor Eduard Andrei eduardandrei20 Data 2 iunie 2019 12:20:11
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

const int dim = 100001;
int noduri, muchii;
vector<int>G[dim];
int grade[dim];

int citire() {

	in >> noduri >> muchii;
	for (int i = 0; i < muchii; i++) {
		int x, y;
		in >> x >> y;
		G[x].push_back(y), G[y].push_back(x), grade[x]++, grade[y]++;
	}

	for (int i = 1; i <= noduri; i++) {
		if (grade[i] & 1) {
			out << "-1\n";
			return 0;
		}
	}

	return 0;
}

stack<int>st;
vector<int>ciclu;

void euler(int start) {
	st.push(start);

	while (st.empty() == false) {
		int nod = st.top();
		
		if (!G[nod].empty()) {
			int y = G[nod].back();
			G[nod].pop_back();
			G[y].erase(find(G[y].begin(), G[y].end(), nod));
			st.push(y);
		}
		else {
			ciclu.push_back(nod);
			st.pop();
		}
	}
	return;
}


int main() {

	if (citire() == -1) {
		return 0;
	}

	euler(1);
	int k = ciclu.size() - 1;
	for (int i = 0; i < k; i++) {
		out << ciclu[i] << " ";
	}

	return 0;
}