Cod sursa(job #2376948)

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

using namespace std;

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

vector<vector<int>> adjList;
vector<int> ciclu;
vector<bool> vizitat;


void euler(int x)
{
	while (adjList[x].empty() == false)
	{
		int vecin;
		for (auto i : adjList[x])
			if (vizitat[i] == false && i != -1)
			{
				vecin = i;
				break;
			}
		int ind1, ind2;
		for (int i = 0; i < adjList[x].size(); i++)
		{
			if (adjList[x][i] == vecin)
			{
				ind1 = i;
				break;
			}
		}
		for (int i = 0; i < adjList[vecin].size(); i++)
		{
			if (adjList[vecin][i] == x)
			{
				ind2 = i;
				break;
			}
		}
		adjList[x].erase(adjList[x].begin() + ind1);
		adjList[vecin].erase(adjList[vecin].begin() + ind2);
		euler(vecin);
	}
	ciclu.push_back(x);
}
int main()
{
	int n, m;
	fin >> n >> m;
	adjList.resize(n + 1);
	vizitat.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		fin >> a >> b;
		adjList[a].push_back(b);
		adjList[b].push_back(a);
	}
	int flag = true;
	for (auto const&a : adjList)
	{
		if (a.size() % 2 == 1)
		{
			flag = false;
			break;
		}
	}
	if (flag == false)
	{
		fout << -1;
		return 0;
	}
	euler(1);
	for (int i = ciclu.size() - 1; i >= 1; i--)
		fout << ciclu[i]<<" ";
	return 0;
}