Cod sursa(job #1333701)

Utilizator anaid96Nasue Diana anaid96 Data 3 februarie 2015 14:59:09
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

FILE *in,*out;

//definitions
#define pb push_back
#define popb pop_back

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

//variables
int nodes, edges;
int node1, node2;

vector<int> graph[sz];
vector<int> answer;

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

int main(void)
{
	in = fopen("ciclueuler.in", "rt");
	out = fopen("ciclueuler.out", "wt");
	
	fscanf(in, "%d%d", &nodes, &edges);
	
	while(edges--)
	{
		fscanf(in, "%d%d", &node1, &node2);
		graph[node1].pb(node2);
		graph[node2].pb(node1);
	}
	
	if(!eulerian())
		fprintf(out,"-1\n");
	else
	{
		euler();
		
		vector<int> :: iterator it, end=answer.end();
		for( it=answer.begin(); it!=end; ++it)
			fprintf(out,"%d ", *it);
		
	}
	
	fclose(in);
	fclose(out);
	return 0;
}

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

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();
}