Cod sursa(job #1917589)

Utilizator horiainfoTurcuman Horia horiainfo Data 9 martie 2017 12:35:48
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define ll long long
using namespace std;

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

struct Edge { int n1, n2; bool used; };

vector<int> sol;
vector<Edge*> node[100002];

void euler(int nod)
{
	while (!node[nod].empty())
	{
		int i = node[nod].size() - 1;

		if (!node[nod][i]->used)
		{
			node[nod][i]->used = true;
			int nxt = node[nod][i]->n1 ^ node[nod][i]->n2 ^ nod;
			node[nod].pop_back();
			euler(nxt);
		}
		else
			node[nod].pop_back();
	}
	sol.push_back(nod);
}

int main()
{
	int n, m;

	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		Edge* edge = new Edge();
		fin >> edge->n1 >> edge->n2;

		node[edge->n1].push_back(edge);
		node[edge->n2].push_back(edge);
	}

	for(int i = 1; i <= n; i ++)
		if (node[i].size() & 1)
		{
			fout << -1;
			return 0;
		}

	euler(1);
	for (int i = 0; i < sol.size() - 1; i++)
		fout << sol[i] << ' ';
	return 0;
}