Cod sursa(job #713042)

Utilizator ms-ninjacristescu liviu ms-ninja Data 14 martie 2012 08:48:47
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#include <stack>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
#define dim 100005
list <int> v[dim*5];
stack <int> stiva;
stack <int> sol;
int viz[dim], n, m, grad[dim];
void read()
{
	int i, a, b;
	fin>>n >>m;
	for(i=1;i<=m;++i)
	{
		fin>>a >>b;
		v[a].push_back(b);
		v[b].push_back(a);
		++grad[a];
		++grad[b];
	}
}
		
int check()
{
	for(int i=1;i<=n;++i)
		if(grad[i]%2==1)
			return 0;
		return 1;
}

void euler()
{
	list <int> ::iterator it;
	int i, next;
	
	for(stiva.push(1);!stiva.empty();)
	{
		int re=stiva.top();
		
		if(v[re].empty()!=0)
		{
			sol.push(re);
			stiva.pop();
		}
		else
		{
			stiva.push(*v[re].begin());
			v[re].pop_front();
			next=stiva.top();
			for(it=v[next].begin();it!=v[next].end();++it)
				if(*it==re)
				{
					v[next].erase(it);
					break;
				}
		}
	}
	
	
	for(;sol.size()>1;sol.pop())
		fout<<sol.top() <<" ";
}
	

int main()
{
	read();
	if(check()==0)
		fout<<"-1";
	else
		euler();
	
	return 0;
}