Cod sursa(job #2654729)

Utilizator StefanSanStanescu Stefan StefanSan Data 2 octombrie 2020 09:28:13
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include      <iostream>
#include      <fstream>
#include      <algorithm>
#include      <queue>
#include      <vector>
#include      <stack>

const int NMAX = 100005;

using namespace std;

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

int n, m;
bool vizitat[5 * NMAX];
vector < pair < int, int > > V[NMAX];
vector < int > solutions;

void dfs(int nodStart) {
	stack < int > ST;
	ST.push(nodStart);
	while (!ST.empty()) {
		int nodCurent = ST.top();
		ST.pop();
		if (V[nodCurent].size() == 0)solutions.push_back(nodCurent);
		else {
			int next = V[nodCurent].back().first;
			int tip = V[nodCurent].back().second;

			V[nodCurent].pop_back();
			ST.push(nodCurent);

			if (!vizitat[tip]) {
				vizitat[tip] = true;
				ST.push(next);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);
	
	in >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		in >> x >> y;
		V[x].push_back(make_pair(y, i));
		V[y].push_back(make_pair(x, i));
	}

	bool ok = true;

	for (int i = 1; i <= n && ok == true; i++) {
		if (V[i].size() % 2 != 0) ok = false;
	}

	if (ok == false)out << "-1";
	else {
		dfs(1);
		solutions.pop_back();
		for (int i = 0; i < solutions.size(); i++) out << solutions[i] << ' ';
	}


	return 0;
	 
}