Cod sursa(job #956069)

Utilizator gabrieligabrieli gabrieli Data 2 iunie 2013 06:17:49
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

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

int main()
{
	int N, m;
	fin >> N >> m;

	vector <vector <int>> G (N+1);
	vector <int> degree (N+1, 0);
	for (int i = m; i; --i)
	{
		int x, y;
		fin >> x >> y;

		G[x].push_back (y);
		G[y].push_back (x);

		degree[x]++;
		degree[y]++;
	}

	for (int v = 1; v <= N; ++v)
		if (degree[v] == 0 || degree[v] % 2 == 1)
		{
			fout << "-1\n";
			fout.close();
			return 0;
		}

	stack <int> vst;
	vst.push (1);
    while (!vst.empty())
	{
		int v = vst.top();

		if (G[v].size() == 0)
		{
			vst.pop();
			if (!vst.empty()) fout << v << ' ';
		}
		else
		{
			int w = G[v].back();
			vst.push (w);
			G[v].pop_back();
			G[w].erase (find (G[w].begin(), G[w].end(), v));
		}
	}

	fout << '\n';
	fout.close();
	return EXIT_SUCCESS;
}