Cod sursa(job #1349790)

Utilizator theprdvtheprdv theprdv Data 20 februarie 2015 14:48:01
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

fstream fout("ciclueuler.out", ios::out);
#define MAXN 100005
vector <int> list[MAXN];
int n, m;

void read()
{
	fstream fin("ciclueuler.in", ios::in);
	fin >> n >> m;
	for (int i = 1, x, y; i <= m; i++)
		fin >> x >> y,
		list[x].push_back(y),
		list[y].push_back(x);
	fin.close();
}
bool is_euler()
{
	for (int i = 1; i <= n; i++)
		if (list[i].size() % 2 != 0 || !list[i].size())		return false;
	return true;
}
void find_cycle()
{
	int next_node;
	stack <int> st;
	vector <int> cycle;
	st.push(1);
	while (!st.empty())
		if (list[st.top()].size())
			next_node = list[st.top()].back(),
			list[st.top()].pop_back(),
			list[next_node].erase(find(list[next_node].begin(), list[next_node].end(), st.top())),
			st.push(next_node);
		else
			cycle.push_back(st.top()),
			st.pop();
	for (int i = 0; i < cycle.size() - 1; i++)
		fout << cycle[i] << ' ';
	fout.close();
}

int main() 
{
	read();
	if (!is_euler())
	{
		fout << "-1\n";
		fout.close();
		return 0;
	}
	find_cycle();

	return 0;
}