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


void BFS(int *, int *,int ** ,int, int);
int DFS(int *, int , int **, int );
int componenti(int **, int );
void lightBFSc(int **, int *, int, int, int*);
int BFScomp(int **, int);
struct node *newNode(int);
struct node* insert(struct node*, int, int *);
int search(struct node*, int);


//DEFINIZIONE DELLA FUNZIONE **BFS**
void BFS(int *A, int *dist, int **pre, int n, int P) {
  int ii, ndp=0, i, d=0, nd=1, m=0, *mark, k=0;
  mark= (int *)calloc(1,sizeof(int)); //inizializzo
  mark[0]=P;
  for(i=0; i<n; i++){
    dist[i]=n;
    *(pre+i)=(int*) calloc(1,sizeof(int));
    }
    dist[P]=0;

  while(nd!=0){
    for(i=m; i<(m+nd); i++){
      for(ii=0;ii<n;ii++){
        if(A[n*mark[i]+ii]==1) {
          if(dist[ii]==(d+1)) {
            k= pre[ii][0]; //alloco pre1
            k++;
            *(pre+ii)= (int*) realloc(*(pre+ii), (k+1)*sizeof(int));
            pre[ii][0]=k;
            pre[ii][k]=mark[i];
            k=0;
            }
            if(dist[ii]==n){
              dist[ii]=d+1; //alloco dist
              ndp++;
              mark= (int*) realloc(mark, (m+nd+ndp)*sizeof(int)); //alloco mark
              mark[m+nd+ndp-1]=ii;
              k= pre[ii][0]; //alloco pre1
              k++;
              *(pre+ii)= (int*) realloc(*(pre+ii), (k+1)*sizeof(int));
              pre[ii][0]=k;
              pre[ii][k]=mark[i];
              k=0;
            }
          }
        }
      }
      m+=nd;
      nd=ndp;
      ndp=0;
      d++;
    }

  free(mark);
  }

  //DEFINIZIONE **DFS**
  int DFS(int *ic, int i, int **J, int nc){
    int s=1, k, j, ii;
    ic[i]=nc;
    k=J[i][0];
    for(j=1; j<=k; j++){
      ii=J[i][j];
      if(ic[ii]==0){
        s+=DFS(ic, ii, J, nc);
      }
    }
    return s;
  }

  //DEFINIZIONE **componenti**
  int componenti(int **J, int n){
    int nc, *ic, *size, i, jj, s;
    ic= (int*) calloc(n,sizeof(int));
    size= (int*) calloc(1,sizeof(int));
    for(jj=0;jj<n;jj++){
      ic[jj]=0;
    }
    nc=0;
    for(i=0;i<n;i++){
      if(ic[i]==0){
        nc++;
        s= DFS(ic, i, J, nc);
        if(nc>1){
          size= (int*) realloc(size, nc*sizeof(int));
          size[nc-1]=s;
        }else{size[0]=s;}
      }
    }
    return nc;
  }

 //****BFS MODIFICATO PER PROGRAMMA SPEEDTEST****

 //DEFINIZIONE **BFScomp**
 int BFScomp(int **J, int n){
   int i, C=0, *comp, *dist;
   comp=(int*)calloc(n, sizeof(int*));
   dist=(int*)calloc(n, sizeof(int*));
   for(i=0; i<n; i++){
     if(comp[i]!=n){
       lightBFSc(J, dist, n, i, comp);
       C++;
     }
   }
   return C;
   free(comp);
   free(dist);
 }

 //DEFINIZIONE **lightBFSc**
 void lightBFSc(int **J, int *dist, int n, int P, int *comp) {
   int ii, ndp=0, i, d=0, nd=1, m=0, *mark, k, marked;
   mark= (int *)calloc(1,sizeof(int)); //inizializzo
   mark[0]=P;
   comp[P]=n;
   for(i=0; i<n; i++) {
     dist[i]=n;
   }
   dist[P]=0;
   while(nd>0 && d<n){
     for(i=m; i<(m+nd); i++) {
         k=J[mark[i]][0]; //è stata usata una struttura dati diversa per velocità
         for(ii=1;ii<=k;ii++){
           marked=J[mark[i]][ii];
             if(dist[marked]==n){
               dist[marked]=d+1; //alloco dist
               ndp++;
               mark= (int*) realloc(mark, (m+nd+ndp)*sizeof(int)); //alloco mark
               mark[m+nd+ndp-1]=marked;
               comp[marked]=n;
             }
         }
       }
   m+=nd;
   nd=ndp;
   ndp=0;
   d++;
   }
   free(mark);
 }

 //DEFINISCO FUNZIONI PER **BST** (struct)
 struct node {
     int key;
     struct node *left, *right;
 };

 struct node *newNode(int item)
 {
     struct node *temp =  (struct node *)malloc(sizeof(struct node));
     temp->key = item;
     temp->left = temp->right = NULL;
     return temp;
 }

 struct node* insert(struct node* node, int key, int *search) {
     if(node==NULL) {
       return newNode(key);
     }
     if(key==node->key){
       search[0]=1;
     }
     if(key < node->key){
           node->left = insert(node->left, key, search);
         }
     if (key > node->key){
           node->right = insert(node->right, key, search);
         }
     return node;

 }
 int search(struct node* node, int key) {
     int A;
     if(node==NULL) {
       return 0;
     }
     if(key==node->key){
       return 1;
     }
     if(key < node->key){
           A=search(node->left, key);
         }
     if (key > node->key){
           A=search(node->left, key);
         }
     return A;

 }