Cod sursa(job #716519)

Utilizator cdascaluDascalu Cristian cdascalu Data 18 martie 2012 22:08:13
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<stdio.h>
#include<vector>
#include<queue>
#include<bitset>
#define Nmax 500001
using namespace std;

int N,M,st[Nmax],gr[Nmax];

queue<int> Q;

vector< pair<int,int> > G[Nmax];

bitset<Nmax> viz;

void read()
{
	FILE*f = fopen("ciclueuler.in","r");
	fscanf(f,"%d%d",&N,&M);
	
	int i,x,y;
	for(i=1;i<=M;++i)
	{
		fscanf(f,"%d%d",&x,&y);
		G[x].push_back(make_pair(y,i));
		G[y].push_back(make_pair(x,i));
		++gr[x];
		++gr[y];
	}
	
	fclose(f);
}
void df(int x)
{
	viz[x] = true;
	for(vector< pair<int,int> >::iterator it = G[x].begin();it!=G[x].end();++it)
		if(viz[it->first] == false)
			df(it->first);
}
void euler()
{
	st[++st[0]] = 1;
	viz.reset();
	
	int nod,vec,ind;
	
	while(st[0])
	{
		nod = st[st[0]];
		if(G[nod].size() == 0)
		{
			Q.push(nod);
			--st[0];
			continue;
		}
		vec = (G[nod].end()-1)->first;
		ind = (G[nod].end()-1)->second;
		G[nod].pop_back();
		if(viz[ind] == false)
		{
			viz[ind] = true;
			st[++st[0]] = vec;
		}
	}
}
int main()
{
	read();
	df(1);
	int ok = 1;
	for(int i=1;i<=N;++i)
		if(viz[i] == false || gr[i] % 2 == 1)
			ok = 0;
	FILE*g = fopen("ciclueuler.out","w");
	if(ok)
	{
		euler();
		for(int i=1, ok = Q.size();i<ok;++i,Q.pop())
			fprintf(g,"%d ",Q.front());
	}
	else
		fprintf(g,"-1");
	fclose(g);
	return 0;
}