Cod sursa(job #969027)

Utilizator tudorv96Tudor Varan tudorv96 Data 3 iulie 2013 12:53:49
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <list>
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector <bool> viz;
vector <int> G, sol;
vector <list <int> > g;
int n, m;
bool res = 1;

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

void dfs(int x) {
	viz[x] = 1;
	for (list <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
		if (!viz[*it])
			dfs (*it);
}

bool grad() {
	for (int i = 1; i <= n; ++i)
		if (G[i] % 2 || (!viz[i] && G[i]))
			return 0;
	return 1;
}

void euler(int x) {
	while (g[x].size()) {
		int y = *g[x].begin();
		g[x].erase(g[x].begin());
		list <int> :: iterator it = g[y].begin();
		while (*it != x)
			++it;
		g[y].erase (it);
		euler(y);
		sol.push_back (x);
	}
}

int main() {
	fin >> n >> m;
	viz.resize(n+1);
	G.resize(n+1);
	g.resize(n+1);
	sol.reserve(m);
	while (m--) {
		int x, y;
		fin >> x >> y;
		if (x != y)
			G[x]++, G[y]++;
		g[x].push_back (y);
		g[y].push_back (x);
	}
	fin.close();
	int x = 1;
	while (!g[x].size() && x <= n)
		++x;
	dfs(x);
	res = grad(); 
	if (res) {
		euler(x);
		for (int i = 1; i <= n; ++i)
			if (g[i].size())
				res = 0;
	}
	if (res)
		for (vector <int> :: reverse_iterator it = sol.rbegin(); it != sol.rend(); ++it)
			fout << *it << " ";
	else
		fout << -1;
	fout.close();
}