Cod sursa(job #1133797)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 5 martie 2014 17:14:45
Problema Ciclu Eulerian Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<vector>
#include<queue>
#define pb push_back
using namespace std;
vector <int> gr[100001];
bool viz[100001];
queue <int> qvf;
vector <int> ciclu;
void bfs(int vf)
{
	int i;
	viz[vf]=1;
	qvf.push(vf);
	while(!qvf.empty())
	{
		vf=qvf.front();
		qvf.pop();
		for(i=0;i<gr[vf].size();i++)
			if(!viz[gr[vf][i]])
			{
				qvf.push(gr[vf][i]);
				viz[gr[vf][i]]=1;
			}
	}
}
bool eulerian(int n)
{
	int i;
	bfs(1);
	for(i=1;i<=n;i++)
		if((!viz[i]) || (gr[i].size()%2==1))
			return 0;
	return 1;
}
void sterge(int vf, int vf2)
{
	vector <int>:: iterator it;
	gr[vf].pop_back();
	for(it=gr[vf2].begin();it!=gr[vf2].end();it++)
		if(*it==vf)
		{
			gr[vf2].erase(it);
			break;
		}
}
void euler(int vf)
{
	int vf2;
	while(gr[vf].size())
	{
		vf2=gr[vf].back();
		sterge(vf,vf2);
		ciclu.pb(vf);
		vf=vf2;
	}
}
int main()
{
	int n,m;
	int i,j;
	int xx,yy;
	ifstream f("ciclueuler.in");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>xx>>yy;
		gr[xx].pb(yy);
		gr[yy].pb(xx);
	}
	f.close();
	ofstream g("ciclueuler.out");
	if(eulerian(n))
	{
		euler(1);
		for(i=0;i<ciclu.size();i++)
			g<<ciclu[i]<<" ";
		g<<'\n';
	}
	else
		g<<"-1\n";
	g.close();
	return 0;
}