Cod sursa(job #2377047)

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

using namespace std;

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

vector<vector<pair<int, int>>> adjList;
vector<int> ciclu;
vector<bool> viz;

void euler(int x)
{
	while (adjList[x].empty() == false)
	{
		auto e = adjList[x].back();
		adjList[x].pop_back();
		if (viz[e.second] == false)
		{
			viz[e.second] = true;
			euler(e.first);
		}
	}
	ciclu.push_back(x);
}
int main()
{
	int n, m;
	fin >> n >> m;
	adjList.resize(n + 1);
	viz.resize(m + 1, false);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		fin >> a >> b;
		adjList[a].push_back({ b, i });
		adjList[b].push_back({ a, i });
	}
	for (int i = 1; i <= n; i++)
	{
		if (adjList[i].size() & 1)
		{
			fout << -1;
			return 0;
		}
	}

	euler(1);
	for (int i = 1; i < ciclu.size(); i++)
		fout << ciclu[i] << " ";
	return 0;
}