Cod sursa(job #941913)

Utilizator forgetHow Si Yu forget Data 20 aprilie 2013 04:58:57
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <list>
using namespace std;

struct edge
{
	int ve;
	list<edge>::iterator it;
};

vector<list<edge> > adjl;
vector<int> circuit;

void dfs(int i)
{
	while (!adjl[i].empty()) {
		int j = adjl[i].front().ve;
		adjl[j].erase(adjl[i].front().it);
		adjl[i].pop_front();
		dfs(j);
	}
	circuit.push_back(i);
}

int main()
{
	ifstream fin("ciclueuler.in");
	ofstream fout("ciclueuler.out");
	int n, m;
	fin >> n >> m;
	adjl.resize(n+1);
	int u, v;
	list<edge>::iterator it1, it2;
	for (int i = 0; i < m; ++i) {
		fin >> u >> v;
		adjl[u].push_back(edge());
		it1 = --adjl[u].end();
		adjl[v].push_back(edge());
		it2 = --adjl[v].end();
		it1->ve = v, it1->it = it2;
		it2->ve = u; it2->it = it1;
	}
	dfs(1);
	if (circuit.size() == m+1)
		if (circuit[0] == circuit[m])
		for (int i = 0; i < m; ++i)
			fout << circuit[i] << ' ';
	else
		fout << -1;
	return 0;
}