Cod sursa(job #630304)

Utilizator ELHoriaHoria Cretescu ELHoria Data 5 noiembrie 2011 11:09:17
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <queue>
#include <list>
#include <stack>

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

const int NMAX = 100002;
int N , M , grad[NMAX];
bool viz[NMAX];
list<int> G[NMAX] , sol;
stack<int> S;

void read_data()
{
	fin>>N>>M;
	for(;M;M--)
	{
		int x , y;
		fin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
		grad[x]++ , grad[y]++;
	}
}

void bfs(int v)
{
	queue<int> Q;
	Q.push(v) , viz[v] = 1;
	while(!Q.empty())
	{
		v = Q.front() , Q.pop();
		for(list<int>::const_iterator it=G[v].begin();it!=G[v].end();++it)
			if(!viz[*it]) viz[*it] = 1 , Q.push(*it);
	}
}

int eulerian()
{
	bfs(1);
	for(int i=1;i<=N;++i)
		if(grad[i]%2 == 1 || !viz[i]) return 0;
	return 1;
}

void sterge(int v,int w)
{
	grad[v]--; grad[w]--;
	G[v].pop_front();
	for(list<int>::iterator it=G[w].begin();it!=G[w].end();++it)
		if(*it==v)
		{
			G[w].erase(it);  
			break;
		}
}

void euler(int v)
{	
	while(true)
	{
		if(G[v].empty()) break;
		int w = G[v].front();
		S.push(v);
		sterge(v,w);
		v = w;
	}
}

void solve()
{
	int v = eulerian();
	if(v)
	{
		do { 
		  euler(v);
		  sol.push_back( v = S.top() ), S.pop();
		}  while(!S.empty());
	}
}

void print_out()
{
	if(!sol.empty())
		for(list<int>::const_iterator it=sol.begin();it!=sol.end();++it)
			fout<<*it<<' ';
	else
		fout<<-1;

	fout<<'\n';
}

int main()
{
	read_data();
	solve();
	print_out();
	return 0;
}