Cod sursa(job #751058)

Utilizator ChallengeMurtaza Alexandru Challenge Data 24 mai 2012 00:24:05
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <vector>

using namespace std;

const char InFile[]="ciclueuler.in";
const char OutFile[]="ciclueuler.out";
const int MaxN=100111;
const int MaxM=500111;

FILE *fin=fopen(InFile,"r");
FILE *fout=fopen(OutFile,"w");

int N,M,x,y,D[MaxN];
vector<int> G[MaxN],sol,S;
char *ptr;

inline int Number()
{
	int sol=0;
	while(!('0'<=*ptr && *ptr<='9'))
	{
		++ptr;
	}

	while('0'<=*ptr && *ptr<='9')
	{
		sol*=10;
		sol+=*ptr-'0';
		++ptr;
	}
	return sol;
}

int main()
{
	fseek(fin,0,SEEK_END);
	int size=ftell(fin);
	rewind(fin);

	ptr=new char[size];

	fread(ptr,1,size,fin);
	fclose(fin);

	N=Number();
	M=Number();
	for(register int i=1;i<=M;++i)
	{
		x=Number();
		y=Number();
		G[x].push_back(y);
		G[y].push_back(x);
		++D[x];
		++D[y];
	}
	
	for(register int i=1;i<=N;++i)
	{
		if(D[i]&1)
		{
			fprintf(fout,"-1");
			return 0;
		}
	}
	
	S.push_back(1);
	while(!S.empty())
	{
		int nod=S.back();
		if(G[nod].size()==0)
		{
			sol.push_back(nod);
			S.pop_back();
		}
		else
		{
			int e=G[nod].back();
			G[nod].pop_back();
			S.push_back(e);
			for(register int i=0;i<G[e].size();++i)
			{
				if(G[e][i]==nod)
				{
					G[e][i]=G[e].back();
					G[e].pop_back();
					break;
				}
			}
		}
	}

	for(register int i=1;i<sol.size();++i)
	{
		fprintf(fout,"%d ",sol[i]);
	}
	fclose(fout);
	return 0;
}