Cod sursa(job #797195)

Utilizator matei_cChristescu Matei matei_c Data 13 octombrie 2012 16:57:49
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

#define maxn 100005
#define maxm 500005

int n,m,grad[maxn],sol[maxm],stiva[maxm] ;
bool sel[maxm] ;
vector < pair<int,int> > v[maxn] ;

bool grad_par()
{
	
	for(int i=1;i<=n;++i)
		if( grad[i] & 1 )
			return false ;
	return true ;
	
}

bool toate_muchiile ()
{
	
	for(int i=1;i<=m;++i)
		if( ! sel[i] )
			return false ;
	return true ;
	
}

void euler ()
{
	
	stiva[ ++stiva[0] ] = 1 ;
	
	while( stiva[0] )
	{
		
		int nod = stiva[ stiva[0] ] ;
		
		if( v[nod].empty() )
		{
			sol[ ++sol[0] ] = stiva[ stiva[0] ] ;
			continue ;
		}
		
		int varf = v[nod].back().first;
		int nrmuchie = v[nod].back().second;
		v[nod].pop_back () ;
		
		if( sel[nrmuchie] == false )
		{
			sel[nrmuchie] = true ;
			stiva[ ++stiva[0] ] = varf ;
		}
	}
}

int main ()
{
	
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=m;++i)
	{
		int x,y ;
		scanf("%d%d",&x,&y);
		v[x].push_back ( make_pair (y, i) ) ;
		v[y].push_back ( make_pair (x, i) ) ;
		++ grad[x] ;
		++ grad[y] ;
	}
	
	if( ! grad_par () )
	{
		printf("-1\n");
		return 0 ;
	}
	
	euler () ;
	
	if( ! toate_muchiile () )
	{
		printf("-1\n");
		return 0 ;
	}
	
	for(int i=1;i<sol[0];++i)
		printf("%d\n",sol[i]);
	
	return 0 ;
	
}