#include <stdio.h>
#include <string.h>
#include <math.h>
//#include <time.h>
#include <stdlib.h>

void aleatcon(int **m, int k, int **a)
{
  int i,j,l,d,dd,g1,sum,n,aristas,c1,c2,c3;
  int * grado, *conex;
  int r;
  char *ch="a";
  void nomemo();

  grado = (int *) malloc(k * sizeof(int)); if (grado==NULL) nomemo();
  conex = (int *) malloc(k * sizeof(int)); if (conex==NULL) nomemo();

  for(i=0;i<k;i++)
    {
      for(j=0;j<k;j++)
	{
	  a[i][j]=0;
	}
    }

  for(i=0;i<k;i++)
    {
      sum=0;
      for(j=0;j<k;j++)
	{
	  sum+=m[i][j];
	}
      a[i][i]=-sum;
    }

  n=1;
  do            //sum!=0
    {
      for(i=0;i<k;i++)
	{
	  for(j=0;j<k;j++)
	    {
	      if (i!=j) {a[i][j]=0;}
	    }
	}
      aristas=0;
      for(j=0;j<k;j++) 
	{
	  grado[j]=-a[j][j];
	  conex[j]=0;
	  aristas+=grado[j];
	  //	  printf("%d,%d ",j,grado[j]);
	}
      aristas=aristas/2;
      l=aristas*10;
      //                  printf("\tnumero inicial de aristas=%d\n",aristas);
      i=maximo(grado,k,0);
      //      do{i=rrand(k);}while(grado[i]<2);
      //              printf("\tnodo conectado inicialmente=%d\n",i);
      conex[i]=1;
      c2=1;
      c3=i;

      //      l=0;
      //      i=0;
      do        // Número de aristas
/*     for(i=0;i<k-1;i++)*/
	{
	  //	  i=0;
	  //   for (j=0;j<k;j++) {printf("%d,%d ",j,grado[j]);}
	  //   printf("\n");
	  do   // ver si hay algún nodo que tenga que conectarse a narices
	    {
	      //	      for (j=0;j<k;j++) {printf("%d,%d ",j,grado[j]);}
	      //	      printf("\n");
	      if(grado[i]>0)
		{
		  d=0;
		  for (j=0;j<k;j++) {if ((a[i][j]==0)&(grado[j]>0)) {d+=1;}}
		}
	      else {d=-1;}
	      i++;
	    }
	  while((i<k) & ((d>grado[i-1]) | (grado[i-1]==0)));
	  if (i!=k)    //tiene que conectarse a narices 
	    {
	      i=i-1; 
	      //	      printf("IF i=%d,%d,%d,%d\n",i,d,grado[i],aristas);
	      //     if (grado[i]> d) {l=k*k; printf("RESETEO\n");}

	      /// CONECTARLO CON TODOS

	      if ((d==0)|(d<grado[i])){l=0;}
	      else
		{

		  d=1;
		  
		  for (j=0;j<k;j++) 
		    {
		      if ((a[i][j]==0)&(grado[j]>0)&(j!=i))
			{
			  a[i][j]=1;
			  a[j][i]=1;
			  grado[i]-=1;
			  grado[j]-=1;
			  conex[i]=1;
			  conex[j]=1;
			  //			l--;
			  aristas--; 
			  //printf("\tarista puesta %d,%d,%d,%d\n",j,aristas,grado[i],grado[j]);
			}
		      if (grado[j]>0) c2++;
		    }	
		}
	      //	      printf("FINIF aristas=%d\n",aristas);
	    }
	  
	  else  //no tiene que conectarse a narices
	    {
	      //	      printf("else ");
	      //  for (j=0;j<k;j++) {printf("%d,%d ",conex[j],grado[j]);}
	      //	      printf("\n");
	      c1=0;
	      do
		{
		  //i=rrand(k); 
		  		  i=maximo(grado,k,i);
		  // que no cierre un ciclo
		  d=-2;
		  if (grado[i]==1)
		    {
		      d=0;//dd=0;
		      for (j=0;j<k;j++) {if ((conex[j]==1)&(grado[j]==0)) {d+=1;}}
		      //		      for (j=0;j<k;j++) {if ((conex[j]==1)&(grado[j]==1)) {dd+=1;}}
		      		      if (conex[i]==1) d--;
		    }
		  c1++;
		  //	  printf("c1=%d ",c1);
		}
	      //	      while((grado[i]==0));
	      while(((grado[i]==0)|(d==1)) & (c1<k*3));
	    
	  //	      printf("i=%d, d=%d\n",i,d);
	    
	      d=0;
	      for (j=0;j<k;j++) {if ((grado[j]>0) & (a[i][j]<1)) {d+=1;}}
	      c1=0;
	      //      	  while ((grado[i]>0) & (grado[i]<d) & (c1<k*k))           /*menor que los nodos que quedan con grado*/
	      //	    {
	      if ((c2==1) & (conex[i]==0)) {r=c3;}
	      else {r=rrand(k);}  //!!!!!!!!!!!!!!!!! que r no me cierre un cliclo
	      //	      	      if (((r>555) & (r<560)) | ((r>2830)&(r<2835))) printf("r=%d\n",r);
	      //	      	      if ((r==557)|(r==2833)) printf("%d**** %d,%d,%d,%d\n",r,a[i][r],grado[r],conex[i],conex[r]);
	      /*	      printf("i=%d,r=%d,gradoi=%d,grador=%d,d=%d,a=%d\n",i,r,grado[i],grado[r],d,a[i][r]);
		for (j=0;j<k;j++) {printf("%d ",grado[j]);}
		printf("\n");
		for (j=0;j<k;j++) {printf("%d ",a[i][j]);}
		printf("\n");
	      */
	      if ((a[i][r]==0) & (grado[r]>0) & ((conex[i]==1) | (conex[r]==1)))
		{
		  g1=0;
                  for (j=0;j<k;j++) {if ((grado[j]>1) & (a[i][j]==0) & ((conex[j]==1)|(conex[i]==1))) {g1=g1+1;}}
		  //      printf("%d,%d,%d",conex[i],conex[r],g1);
		  if ((grado[i]>1) | (grado[r]>1) | (g1==0))
		    {
		      a[i][r]=1;
		      a[r][i]=1;
		      grado[i]-=1;
		      grado[r]-=1;
		      //		      if ((conex[i]==1) | (conex[r]==1))
		      //{
		      conex[i]=1;
		      conex[r]=1;
		      aristas--;
		      if (grado[r]>0) c2++;
		      //		      if (grado[i]==0) c2--;
		      //		      		      printf("--------------------------arista; %d %d\n",i,r);
		      //  printf("\taristas=%d,%d\n",aristas,r);
		      //}
		    }
		}	    
	      //  c1++;
	      /*	      	      if (c1==9000) 
		{
		  printf("i=%d,c11=%d,d=%d,l=%d\n ",i,c1,d,l);
		  c2=0;
		  for (j=0;j<k;j++) {if (grado[j]>0) {printf("%d,%d,%d,%d ",j,grado[j],a[i][j],conex[j]);c2++;}}
		  printf("\nc2=%d\n",c2);
		  exit(1);
		  }*/
	      //	    } 
	      l--;
	    }
	  //	  printf("l=%d ",l);
	  //	  printf("fin bucle %d,%d,%d\n",l,d,aristas);
	}
      while ((l>0)&(d>0)&(aristas>0));
      sum=0;c1=0;
      for (j=0;j<k;j++) {sum+=grado[j];/*if (grado[j]!=0) {printf("%d,%d,%d ",j,grado[j],conex[j]);c1++;}*/}
      //            printf("\n n=%d\txxxxxxxxxxxxxxxxxx suma=%d xxxxxxxxxxxxxxxxxxxxxx, num=%d,%d \n",n,sum,c1,l);
            n++;
    }
  while(sum!=0);
  //  printf("\n *** ACABE BUCLE *** \n");

  /*  printf("\n");
      for(j=0;j<k;j++) {printf("%d ",conex[j]);}
      printf("\n");
  */
  /*  for (i=0;i<k;i++)
      {
      free(a[i]);
      }
    free(a);
  */

  for(i=0;i<k;i++)
    {
      a[i][i]=0;      
    }

  free(grado);
  free(conex);

  //  return(a);
}  

int maximo(int *grado,int k,int ant)
{
  int i,m;
  m=0;
  for (i=1;i<k;i++)
    {
      if ((grado[i]>grado[m]) | ((grado[i]==grado[m]) & (i!=ant)))
	{
	  m=i;
	}
    }
  return(m);
}

int rrand(int k)
{
  return((int) lrand48()/pow(2,31)*k);
}

