//#include "lapack.h"
#include<math.h>
#include <stdio.h>
#include <stdlib.h>


void principal(int **m,int *k, char **nodos)
{
  int i,j,c,sum,ncon,maxc,otro;
  //  double           * A,*W, *WORK;
  int **A;
  int *conjunto,*size;
  //  double con;
  void nomemo(), suma();


  A = (int **) malloc((*k) * sizeof(int *)); if (A==NULL) nomemo();
  for (i=0;i<*k;i++)
    {
      A[i] = (int *) malloc ((*k) * sizeof(int)); if (A[i]==NULL) nomemo();
    }
  conjunto= (int *) malloc ((*k) * sizeof(int)); if (conjunto==NULL) nomemo();
  //  ncon=0;

  for(i=0;i<*k;i++)
    {
      m[i][i]=1;
      conjunto[i]=0;
      for(j=0;j<*k;j++)
	{
	  A[i][j]=0;
	}
    }
  
  A[0][0]=1;
  ncon=1;


  for(i=0;i<*k;i++)
    {
      c=0;
      otro=-1;
      while(c<ncon)
	{
	  if (comun(m,i,A,c,*k))
	    {
       	      if (otro<0)
		{
		  suma(m,i,A,c,*k);
		  conjunto[i]=c;
		  otro=c;		  
		 }
	      else     // Y si se solapa con varios????? (solapar)
		{
		  suma(A,c,A,otro,*k);
		  for(j=0;j<i;j++) {if(conjunto[j]==c) {conjunto[j]=otro;}}
		  //		  reset(A,c,*k);
		  for (j=0;j<*k;j++) {A[c][j]=0;}
		}
	    }
	  c++;
	}
      if (otro<0)
	{
	  suma(m,i,A,ncon,*k);
	  conjunto[i]=ncon;
	  ncon++;
	}
    }
  
  //  ncon--;

  // ver cual es el conjunto más grande
  
  size = (int *) malloc (ncon * sizeof(int)); if (size==NULL) nomemo();
  for (i=0;i<ncon;i++)
    {
      size[i]=0;
    }
  for (i=0;i<*k;i++)
    {
      size[conjunto[i]]++;
    }
  maxc=0;
  for (i=0;i<ncon;i++)
    {
      if(size[i]>size[maxc]) {maxc=i;}
    }
  //    printf("El conjunto más grande es el %d con %d nodos\n",maxc,size[maxc]);
  j=0;
  //    printf("conjunto grande= ");
  for (i=0;i<*k;i++)
    {
      if(conjunto[i]==maxc) 
	{
	  conjunto[j]=i;
	  j++;
	  // printf("%s ",nodos[i]);
	}
    }
  //    printf("\n");
  
  //  printf("conjunto grande impreso\n");
  // construir la nueva matriz del conjunto más grande
    
  for (i=0;i<size[maxc]-1;i++)
    //    for (i=0;i<size[maxc];i++)
    {
      for (j=i+1;j<size[maxc];j++)
	//for (j=0;j<size[maxc];j++)
	{
	  A[i][j]=0;
	  if (m[conjunto[i]][conjunto[j]]==1) {A[i][j]=1;A[j][i]=1;}
	  //	  	 printf("%d,%d ",A[i][j],m[i][j]);
	}
	//           printf("\n");
    }

  //   printf("matriz A construida\n");
 
  
  for (i=0;i<size[maxc]-1;i++)
    //for (i=0;i<size[maxc];i++)
    {
      for (j=i+1;j<size[maxc];j++)
	//for (j=0;j<size[maxc];j++)
	{
	  m[i][j]=A[i][j];
	  m[j][i]=A[i][j];
	  //  		 printf("%d,%d ",A[i][j],m[i][j]);
	}
      //  printf("\n");
    }
  
  //  m=A;
  
  //  printf("m=%d\n",m);
  
  //   printf("matriz m construida\n");
  
  for (i=0;i<*k;i++)
    {
      free(A[i]);
    }  
  free(A);
  free(conjunto);
  free(size);

  *k=size[maxc];

  //  return(m);
}


int comun(int **m, int i, int **A, int c, int k)
{
  int j,sum;
  sum=0;

  for(j=0;j<k;j++)
    {
      if((m[i][j]>0)&(A[c][j]>0)) {sum++;}
    }

  return((sum>0));
}

void suma(int **m, int i, int **A, int c, int k)
{
  int j;
  for(j=0;j<k;j++)
    {
      A[c][j]+=m[i][j];
    }
}
