Cod sursa(job #1342592)

Utilizator ooptNemes Alin oopt Data 14 februarie 2015 11:34:20
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 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 v ) {
    while( true ) {
        if( V[v].empty() )
            break;
        int w = V[v][V[v].size()-1];
        S.push( v );
        // Stergere muchie
        V[v].pop_back();
        for (unsigned i=0;i<V[w].size();i++)
            if (V[w][i] == v) {
                V[w].erase(V[w].begin() + i);
                break;
            }
        v = w;
    }
}

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;
}