Cod sursa(job #2544608)

Utilizator Iulia25Hosu Iulia Iulia25 Data 12 februarie 2020 11:58:36
Problema Ciclu Eulerian Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 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;
  for (auto it : v[nod])	{
		if (!viz[it])
			dfs(it);
	}
}

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;
}