Cod sursa(job #1365717)

Utilizator Aavatar36Russu Vadim Aavatar36 Data 28 februarie 2015 14:39:06
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <stack>
std::ifstream fin("ciclueuler.in");
std::ofstream fout("ciclueuler.out");
int n, m;
std::vector<int> v[100010];
std::stack<int> temp, final;
int main()
{
	fin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int a, b;
		fin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i = 1; i <= n ; ++i)
	{
		if (v[i].size() % 2 == 1) {
			fout << "-1";
			return 0;
		}
	}
	temp.push(1);
	int nex, front = 1;
	while (!temp.empty()) {
		if (v[front].empty()) {
			final.push(temp.top());
			temp.pop();
			if (temp.empty()) {
				continue;
			}
			front = temp.top();
			continue;
		}
		nex = *(v[front].begin());
		for (std::vector<int>::iterator it = v[nex].begin(); it != v[nex].end(); ++it)
		{
			if (*it == front) {
				v[nex].erase(it);
				break;
			}
		}
		temp.push(*(v[front].begin()));
		v[front].erase(v[front].begin());
		front = nex;
	}

	while (final.size()!=1) {
		fout << final.top() << " ";
		final.pop();
	}
	return 0;

}