Cod sursa(job #3005319)

Utilizator FulopSergiuFulop Sergiu FulopSergiu Data 16 martie 2023 21:22:21
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;

struct Edge {
	int x, y;
};

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

VVI G;
VB v;
VI ce;
vector<Edge> E;
int n, m;

void CitesteGraf();
void Dfs(int x);
bool EsteEulerian();
void ScrieCiclu();

int main()
{
	CitesteGraf();
	if (!EsteEulerian())
		fout << -1;
	else
	{
		Dfs(1);
		ScrieCiclu();
	}
	
	return 0;
}

void Dfs(int x)
{
	ce.emplace_back(x);
	for (int e : G[x])
	{
		if (v[e]) continue;
		v[e] = true;
		E[e].x == x ? Dfs(E[e].y) : Dfs(E[e].x);
	}
}

void CitesteGraf()
{
	fin >> n >> m;
	G = VVI(n + 1);
	v = VB(m + 1);
	E = vector<Edge>(m + 1);
	
	int x, y;
	for (int i = 1; i <= m; ++i)
	{
		fin >> x >> y;
		G[x].emplace_back(i);
		G[y].emplace_back(i);
		E[i] = {x, y};
	}
}

bool EsteEulerian()
{
	for (int x = 1; x <= n; ++x)
		if (G[x].size() % 2 == 1)
			return false;
			
	return true;
}

void ScrieCiclu()
{
	for (int x : ce)
		fout << x << ' ';
}