Cod sursa(job #815492)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 17 noiembrie 2012 06:57:29
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <cstdio>
#include <cstring>
#include <list>
#include <stack>
#include <vector>

using namespace std;

inline int next_int() {
	int n = 0;
	char c = getchar_unlocked();
	while (!('0' <= c && c <= '9')) {
		c = getchar_unlocked();
	}
	while ('0' <= c && c <= '9') {
		n = n * 10 + c - '0';
		c = getchar_unlocked();
	}
	return n;
}

const int V = 100000 + 1;
const int E = 500000 + 500000;

int deg[V], root[V], seen[E];
list<int> G[V];
vector<int> tour;
stack<int> stk;

int find(int u) {
	return (root[u] == u) ? (u) : (root[u] = find(root[u]));
}

inline void merge(int u, int v) {
	root[find(u)] = find(v);
}

inline void cycle(int u) {
	while (!G[u].empty()) {
		stk.push(u);
		int v = G[u].front(); G[u].pop_front();
		for (list<int>::iterator it = G[v].begin(); it != G[v].end(); it++) {
			if (*it == u) {
				G[v].erase(it);
				break;
			}
		}
		u = v;
	}
}

inline void find_euler_tour(int u) {
	stk.push(u);
	while (!stk.empty()) {
		u = stk.top(); stk.pop();
		cycle(u);
		tour.push_back(u);
	}
}

int main() {
	freopen("ciclueuler.in", "r", stdin);
	freopen("ciclueuler.out", "w", stdout);
	const int n = next_int();
	const int m = next_int();
	for (int i = 1; i <= n; i++) {
		root[i] = i;
	}
	for (int i = 0; i < m; i++) {
		int u = next_int(), v = next_int();
		deg[u]++, deg[v]++;
		G[u].push_back(v), G[v].push_back(u);
		merge(u, v);
	}
	int eulerian = true;
	for (int i = 1; i <= n; i++) {
		if ((deg[i] & 1) || find(i) != find(1)) {
			eulerian = false;
		}
	}
	if (eulerian) {
		find_euler_tour(1);
		for (int i = tour.size() - 1; i >= 0; i--) {
			printf("%d ", tour[i]);
		}
	} else {
		printf("-1");
	}
	return 0;
}