Cod sursa(job #2377045)

Utilizator alex.mercan2014Mercan Alexandru alex.mercan2014 Data 8 martie 2019 21:11:27
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

struct edge
{
	int nod, id;
	edge(int a, int b)
	{
		nod = a;
		id = b;
	}
};
int len = 0;
vector<vector<edge>> adl;
vector<bool> viz(500010, false);
vector<int> cycle(500010);

void euler(int nod)
{
	while (adl[nod].empty() == false)
	{
		auto e = adl[nod].back();
		adl[nod].pop_back();
		if (!viz[e.id])
		{
			viz[e.id] = true;
			euler(e.nod);
		}
	}
	cycle[len++] = nod;
}

int main()
{
	int n, m;
	fin >> n >> m;
	adl.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int x, y;
		fin >> x >> y;
		adl[x].push_back(edge(y, i));
		adl[y].push_back(edge(x, i));
	}
	for (int i = 1; i <= n; i++)
		if (adl[i].size() & 1)
		{
			fout << "-1\n";
			return 0;
		}
	euler(1);
	for (int i = 1; i < len; i++)
		fout << cycle[i] << " ";
	return 0;
}