Cod sursa(job #1124842)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 26 februarie 2014 14:01:19
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

int n, m, grad[100005];
vector<int> g[100005], res;
pair<int, int> edge[500005];
bool vis[500005];

inline void euler(const int &node)
{
	while (g[node].size())
	{
		int next = g[node].back(); g[node].pop_back();
		if (!vis[next])
		{
			vis[next] = true;
			euler(edge[next].first + edge[next].second - node);
		}
	}
	res.push_back(node);
}

int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		fin >> edge[i].first >> edge[i].second;
		++grad[edge[i].first];
		++grad[edge[i].second];
		g[edge[i].first].push_back(i);
		g[edge[i].second].push_back(i);
	}
	
	for (int i = 1; i <= n; ++i)
		if (grad[i] % 2)
		{
			fout << "-1\n";
			return 0;
		}
	
	euler(1);
	
	for (size_t i = 0; i < res.size() - 1; ++i)
		fout << res[i] << ' ';
	fout << '\n';
	
	fin.close();
	fout.close();
}