Cod sursa(job #1342595)

Utilizator ooptNemes Alin oopt Data 14 februarie 2015 11:36:59
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
// ciclueuler
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stack>

#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];
bool viz[NMax];

stack<int> S;
vector<int> sol;

void dlt(int x, int y) {
	V[x].pop_back();
	for (unsigned i=0;i<V[y].size();i++)
		if (V[y][i] == x) {
			V[y].erase(V[y].begin()+i);
			return;
		}
}

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

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

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

void goEuler(int node) {
	while (true) {
		if (V[node].empty())
			break;
		int v = V[node][V[node].size()-1];
		S.push(node);
		V[node].pop_back();
		for (int i=0;i<V[v].size();i++)
			if (V[v][i] == node) {
				V[v].erase(V[v].begin()+i);
				break;
			}
		node = v;
	}
}

void solve() {
	if (!conex()) {
		g<<-1<<'\n';
		return;
	}

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

	if (!admite) {
		g<<-1<<'\n';
		return;
	}

	int v = 1;
	do {
		goEuler(v);
		v = S.top(); S.pop();
		sol.pb(v);
	} while (!S.empty());
}

int main() {

	read();
	solve();
	for (unsigned i=0;i<sol.size();i++)
		g<<sol[i]<<' ';

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