Cod sursa(job #1226406)

Utilizator vladrochianVlad Rochian vladrochian Data 5 septembrie 2014 13:14:30
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <list>
#include <stack>
using namespace std;
const int NMAX = 100005;

int N, M;
bool viz[NMAX];
list<int> G[NMAX];
stack<int> st;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

void dfs(int node) {
	viz[node] = 1;
	for (int son : G[node])
		if (!viz[son])
			dfs(son);
}

void Euler(int node) {
	while (!G[node].empty()) {
		st.push(node);
		int nb = G[node].front();
		G[node].pop_front();
		list<int>::iterator it;
		for (it = G[nb].begin(); *it != node; ++it);
		G[nb].erase(it);
		node = nb;
	}
}

int main() {
	fin >> N >> M;
	while (M--) {
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1);
	for (int i = 1; i <= N; ++i)
		if (!viz[i] || G[i].size() & 1) {
			fout << "-1\n";
			return 0;
		}

	int node = 1;
	do {
		Euler(node);
		node = st.top();
		st.pop();
		fout << node << " ";
	} while (!st.empty());
	return 0;
}