#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

struct vertex {
  int id;
  struct vertex *next;
};
typedef struct vertex* verticepunt;   //

/*Structure for dfs */
struct visitaVertice {
  int color; //
  int p;  //
  int d;  //
  int f;  // time to vertex
};

//new vertex
verticepunt newVertex(){
  verticepunt v;
  v=(verticepunt)malloc(sizeof(struct vertex));
  v->next=NULL;
  return v;
}
/*INIT*/
void init(verticepunt list[],int n){
  int i;
  for(i=0;i<n;i++)
    list[i]=NULL;

}

/*INIT DFS*/
void initdfs(struct visitaVertice dfsData[],int n){
  int i;
  for(i=0;i<n;i++){
    dfsData[i].color=0;
    dfsData[i].p=-1;
    dfsData[i].d=0;
    dfsData[i].f=0;
  }
}

/*ADD EDGE*/
void AdjList(verticepunt list[],int n){
     int k,i,j;
    // int temp; caloclo del tempo computazionale
     verticepunt nuovo,p;
     for(i=1;i<n;i++){
       for(j=0;j<i;j++){
         k= randomGen(n);
         if(k==1){
           nuovo=newpunt();
           nuovo->id=i;
           p=list[j];
           if(p==NULL){
             list[j]=nuovo;
           //  temp=temp+1;
           } else {     //caso in cui sia diverso da 1
               while(p->next!=NULL)
               p->next=nuovo;

             }
           }
         }
       }
        //return (temp)
}



//Random genenrator
int randomGen(int end){
    int fine;
    fine= end -1;
      srand((unsigned)time(0));
    int generated = rand() % fine + 1;
    return generated;
}


/**DFS*/
void dfs(verticepunt list[],int n){
   int i;
   verticepunt p;
   struct visitaVertice dfsdata[n];  //Struttura dati che contiene i dati dfs
   initdfs(dfsdata,n);           //Inizializza tale lista
   tempo=0;
   for(i=0;i<n;i++){             //Per ogni v appartenente a G.V
     if(dfsdata[i].color==0)     //Colore bianco
    dfs_visit(list,dfsdata,i);

   }

}
/*DFS VISIT*/
void dfs_visit(verticepunt list[],struct visitaVertice dfsdata[],int i){
  verticepunt p,punt,nuovo;
  int k;

  tempo=tempo +1;
  dfsdata[i].color=1; //Colore grigio
  dfsdata[i].d=tempo;

  p=list[i];
  while(p!=NULL){
    k=p->id;
    if(dfsdata[k].color==0){
      dfsdata[k].p=i;

    }
    p=p->next;
  }
  dfsdata[i].color=2;   //Colore nero
  tempo=tempo+1;
  dfsdata[i].f=tempo;

  }

/*transposed  OF Graph*/
verticepunt getTrasposta(verticepunt list[],int n)
{
   verticepunt trasposta[n];
    verticepunt e;
    verticepunt pT;
   /*faccio scorrere array dei vertici*/
     int   j;
   for(j=0;j<n;j++){
       e=list[j];
   pT=inversion(e);
    trasposta[j]=pT;
          }
   return trasposta;
}

/*now i have a error !!!!!!*/
void inversion(verticepunt p) {
 verticepunt q, q1=NULL;
 int i=0;
 while (p != NULL) {
 q =(verticepunt)malloc(sizeof(struct vertex));
 q->id = p->id;
 q1 = q;
 p = p->next;
 }
 return(q1);
 }

int main(int argc, char** argv) {

    return (EXIT_SUCCESS);
}