Cod sursa(job #2544622)

Utilizator Iulia25Hosu Iulia Iulia25 Data 12 februarie 2020 12:04:30
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>

using namespace std;

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

int n, m, x, y, nr;
int from[500005], to[500005], ciclu[500005];
bool viz[100005];
vector <int> v[100005];

void dfs(int nod)	 {
	viz[nod] = true;
	int w;
	for (auto it : v[nod])	{
		if (nod == to[it])
			w = from[it];
		else
			w = to[it];
		if (!viz[w])
			dfs(w);
	}
}

bool conex()	{
	for (int i = 1; i <= n; ++i)
		if (!viz[i])
			return false;
	return true;
}

bool grad_par()	 {
	for (int i = 1; i <= n; ++i)
		if (v[i].size() % 2 == 1)
			return false;
	return true;
}

void euler(int nod)	 {
	int w;
	for (auto it : v[nod])	{
		if (to[it] == 0)
			continue;
		if (to[it] == nod)
			w = from[it];
		else
			w = to[it];
		to[it] = from[it] = 0;
		euler(w);
	}
	ciclu[++nr] = nod;
}

int main()	{
	fin >> n >> m;
	for (int i = 1; i <= m; ++i)	{
		fin >> x >> y;
		v[x].push_back(i);
		v[y].push_back(i);
		from[i] = x;
		to[i] = y;
	}
	dfs(1);
	if (!conex() || !grad_par())	 {
		fout << -1;
		return 0;
	}
	euler(1);
	for (int i = 1; i < nr; ++i)
		fout << ciclu[i] << ' ';
	return 0;
}