Cod sursa(job #393494)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 9 februarie 2010 15:37:33
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<stdio.h>
#include<vector>
#define Nmax 100010
#define Mmax 500010
using namespace std;

int n,m,i,j,a,b,S[Mmax],viz[Nmax],grad[Nmax],k,M[Mmax];
vector< pair <int,int > > V[Nmax];

void dfs(int nod)
{
	viz[nod]=1;
	int i,N=V[nod].size();
	
	for(i=0;i<N;i++)
		if(!viz[V[nod][i].first])
			dfs(V[nod][i].first);
}

void euler(int nod)
{
	int i,N=V[nod].size();
	
	for(i=0;i<N;i++)
		if(M[V[nod][i].second])
		{
			M[V[nod][i].second]=0;
			euler(V[nod][i].first);
		}
	S[++k]=nod;
}

int main()
{
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&a,&b);
		
		grad[a]++;
		grad[b]++;
		M[i]=1;
		V[a].push_back(make_pair(b,i));
		V[b].push_back(make_pair(a,i));
	}
	dfs(1);
	
	for(i=1;i<=n;i++)
	{
		if(grad[i]&1) {printf("-1");return 0;}
		if(!viz[i])   {printf("-1");return 0;}
	}

	euler(1);
	
	for(i=m+1;i>1;i--)
		printf("%d ",S[i]);
	return 0;
}