Cod sursa(job #876943)

Utilizator fhandreiAndrei Hareza fhandrei Data 12 februarie 2013 13:24:48
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
// Include
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

// Definitii
#define pb push_back
#define popb pop_back

// Constante
const int sz = (int)1e5+1;

// Functii
bool eulerian();
void euler();

// Variabile
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");

bool visited[sz];
int nodes, edges;

vector<int> graph[sz];

vector<int> answer;

// Main
int main()
{
	in >> nodes >> edges;
	
	int rFrom, rTo;
	while(edges--)
	{
		in >> rFrom >> rTo;
		graph[rFrom].pb(rTo);
		graph[rTo].pb(rFrom);
	}
	
	if(!eulerian())
	{
		out << "-1\n";
		in.close();
		out.close();
		return 0;
	}
	
	euler();
	
	vector<int>::iterator it, end=answer.end();
	for(it=answer.begin() ; it!=end ; ++it)
		out << *it << ' ';
	
	in.close();
	out.close();
	return 0;
}

void euler()
{
	stack<int> st;
	st.push(1);
	
	while(!st.empty())
	{
		int current = st.top();
		while(!graph[current].empty())
		{
			int nextNode = *graph[current].begin();
			graph[nextNode].erase(find(graph[nextNode].begin(), graph[nextNode].end(), current));
			graph[current].erase(graph[current].begin());
			
			st.push(nextNode);
			current = nextNode;
		}
		
		answer.pb(current);
		st.pop();
	}
	
	answer.popb();
}



bool eulerian()
{
	for(int i=1 ; i<=nodes ; ++i)
		if(graph[i].size()&1)
			return false;
	
	return true;
}