Cod sursa(job #1361045)

Utilizator ooptNemes Alin oopt Data 25 februarie 2015 19:19:47
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
// ciclueuler
#include <iostream>
#include <fstream>
#include <vector>

#define pb push_back
#define NMax 100005

using namespace std;

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

int n, m;
vector<int> V[NMax];
vector<int> sol;

void read() {
	f>>n>>m;
	for (int i=1;i<=m;i++) {
		int a, b;
		f>>a>>b;
		V[a].pb(b);
		V[b].pb(a);
	}
}

void go(int node) {
	sol.pb(node);
	while (!V[node].empty()) {
		int vecin = V[node][V[node].size()-1];
		V[node].pop_back();
		for (unsigned i=0;i<V[vecin].size();i++)
			if (V[vecin][i] == node) {
				V[vecin].erase(V[vecin].begin() + i);
				break;
			}

		go(vecin);
	}
}
bool viz[NMax];
void dfs(int node) {
	viz[node] = true;
	for (int i=0;i<V[node].size();i++)
		if (!viz[V[node][i]])
			dfs(V[node][i]);
}

bool isEuler() {

	bool ok1 = true;
	for (int i=1;i<=n;i++)
		if (V[i].size()%2 != 0)
			ok1 = false;

	if (!ok1) return false;
	dfs(1);
	for (int i=1;i<=n;i++)
		if (!viz[i]) {
			return false;}

	return true;
}

int main() {
	
	read();
	if (isEuler()) {
		go(1);
	sol.pop_back();
	for (auto i=sol.begin();i!=sol.end();i++)
		g<<(*i)<<' ';
}else {
	g<<-1<<'\n';
}

	f.close(); g.close();
	return 0;
}