Cod sursa(job #2651874)

Utilizator irimia_alexIrimia Alex irimia_alex Data 23 septembrie 2020 18:45:03
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100005

using namespace std;

vector<pair<int,int>> g[NMAX];
vector<int> cycle;
vector<bool> used;

void dfs(int u) {
	vector<int> vert;
	vert.push_back(u);
	while (!vert.empty()) {
		u = vert.back();
		if (!g[u].empty()) {
			while (!g[u].empty()) {
				auto v = g[u].back();
				if (!used[v.second]) {
					used[v.second] = true;
					g[u].pop_back();
					vert.push_back(v.first);
					break;
				}
				else
					g[u].pop_back();
			}
		}
		else {
			cycle.push_back(u);
			vert.pop_back();
		}
	}

}

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

	int n, m;

	fin >> n >> m;

	for (int i = 0;i < m;++i) {
		int x, y;
		fin >> x >> y;
		used.push_back(false);
		g[x].push_back({ y,i });
		g[y].push_back({ x,i });
	}

	dfs(1);
	if (cycle.size() - 1 < m)
		fout << "-1";
	else
		for (auto u : cycle)
			fout << u << ' ';

	return 0;
}