Cod sursa(job #1361095)

Utilizator ooptNemes Alin oopt Data 25 februarie 2015 19:36:13
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 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;
int node;
int vecin;
vector<int> old;
unsigned i;

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() {
	old.push_back(node);
	while (!V[node].empty()) {
		vecin = V[node][V[node].size()-1];
		V[node].pop_back();
		for (i=0;i<V[vecin].size();i++)
			if (V[vecin][i] == node) {
				V[vecin].erase(V[vecin].begin() + i);
				break;
			}

		node = vecin;
		go();
		node = old[old.size()-1];
	}
	old.pop_back();
	sol.pb(node);
}
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()) {
		
		node=1;go();
	sol.pop_back();
	for (auto i=sol.begin();i!=sol.end();i++)
		g<<(*i)<<' ';
}else {
	g<<-1<<'\n';
}

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