Cod sursa(job #954415)

Utilizator BitOneSAlexandru BitOne Data 29 mai 2013 09:48:40
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stack>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <iterator>
#include <algorithm>


using namespace std;

const int NMAX = 100011;


bool was[NMAX];
int d[NMAX];
vector<int> S, ans;
vector<int> G[NMAX];

inline int numberOfNodes(int x)
{
	was[x] = true;
	int count = 1;
	for(auto& y : G[x])
	{
		if(!was[y])
			count += numberOfNodes(y);
	}
	
	return count;
}

inline void euler(int x)
{
	int y;
	
	while(!G[x].empty())
	{
		y = G[x].back(); G[x].pop_back();
		G[y].erase(find(G[y].begin(), G[y].end(), x));
		
		S.push_back(x);
		x = y;		
	}
}

int main()
{
	int N, M, x, y, i;
	ifstream in("ciclueuler.in");
	ofstream out("ciclueuler.out");
	
	//freopen("input.in", "rt", stdin);
	
	for(in >> N >> M; M; --M)
	{
		in >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
		++d[x]; ++d[y];
	}
	
	for(i = 1; i <= N; ++i) 
	{
		if(d[i] % 2)
		{
			out << "-1";
			return EXIT_SUCCESS;
		}
	}
	if(N != numberOfNodes(1)) {out << "-1"; return EXIT_SUCCESS;}
	
	x = 1;
	do {
			euler(x);
			ans.push_back(x = S.back()); S.pop_back();
 	   }while(!S.empty());
	   
	copy(ans.rbegin(), ans.rend(), ostream_iterator<int>(out, " "));
}