Cod sursa(job #1982723)

Utilizator xSliveSergiu xSlive Data 20 mai 2017 01:27:12
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#define CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <unordered_map>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

#define NMAX 100010
#define MMAX 500010

vector<int> vecini[NMAX];
int nNodes, nEdges;
vector<int> eul;
int grad[NMAX];

void euler(int start)
{
	stack<int> stack;
	stack.push(start);
	int el;
	int newElement;
	while(!stack.empty())
	{
		el = stack.top();
		if(vecini[el].size() > 0)
		{
			newElement = vecini[el].back();
			vecini[el].pop_back();
			vecini[newElement].erase(find(vecini[newElement].begin(), vecini[newElement].end(), el));
			stack.push(newElement);
		}
		else
		{
			eul.push_back(el);
			stack.pop();
		}
	}
}

int main()
{
	int val1,val2;
	int start;
	
	f >> nNodes >> nEdges;

	for (int i = 0; i < nEdges;i++)
	{
		f >> val1 >> val2;
		vecini[val1].push_back(val2);
		vecini[val2].push_back(val1);
		grad[val1]++;
		grad[val2]++;
	}
	for (int i = 1; i <= nNodes;i++)
	{
		if(grad[i] % 2)
		{
			g << -1;
			return 0;
		}
	}
	
	start = 1;
	euler(start);
	for (int i = 1; i<eul.size(); i++)
		g << eul[i] << " ";
	return 0;
}