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

#define N 4 // Nombre de sommets
#define A 5 // Nombre d'arcs

typedef int sommet;
typedef sommet graphe1[2*A];

typedef char bool;
typedef bool graphe2[N][N];

typedef struct maillon *liste;
struct maillon {sommet s; liste suite;};
typedef liste graphe3[N];

void afft(int *t,int i) { while(i--) printf(" %d",*t++); printf("\n"); }
void g1g2(graphe1 g1, graphe2 g2)
{ int i, j, k;
  //initialisation de g2 à 0
  for(i = 0; i < N; i++) for(j = 0; j < N; j++) g2[i][j]=0;
  for(k = 0; k < 2 * A; k+=2) g2[g1[k]][g1[k+1]] = 1;
}
void g2g1(graphe2 g2, graphe1 g1)
{ int i, j, k=0;
  for(i=0; i<N; i++) for(j = 0; j < N; j++) if(g2[i][j]) g1[k++]=i,	g1[k++]=j;
}
void g3g1(graphe3 g3, graphe1 g1)
{ int i, k=0;
  liste p;
  for(i = 0; i < N; i++) for(p=g3[i];p;p=p->suite) g1[k++]=i, g1[k++]=p->s;
}
void g3g2(graphe3 g3, graphe2 g2)
{ int i,j;
  liste p;
  for(i = 0; i < N; i++) for(j = 0; j < N; j++) g2[i][j] = 0;
  for(i = 0; i < N; i++) for(p=g3[i];p;p=p->suite) g2[i][p->s]=1;
}
void g1g3(graphe1 g1, graphe3 g3)
{ int i, k;
  for(i = 0; i < N; i++) g3[i]=0;
  for(k = 0; k < 2*A; k+=2)
  {	const int i = g1[k], j = g1[k+1];
	liste p = malloc(sizeof(*p));
	p -> suite = g3[i];
	g3[i] = p;
	p -> s = j;
  }
}
void g2g3(graphe2 g2, graphe3 g3)
{ int i, j;
  for(i = 0; i < N; i++) g3[i] = 0;
  for(i = 0; i < N; i++) for(j = 0; j < N; j++)	if(g2[i][j])
  {				//On ajoute j en tête de la liste g3[i]
    liste p = malloc(sizeof(*p));
    p->suite = g3[i];
    g3[i] = p;
    p->s = j;
  }
}
void affg1(graphe1 g1){
	int k;
	for(k = 0; k < 2*A; k += 2)
    { int i = g1[k], j = g1[k+1];
	  printf("%d --> %d, ", i, j);
	}
	printf("\n");
}
void affg2(graphe2 g2){
	int i, j;
	for(i = 0; i < N; i++) for(j = 0; j < N; j++) if(g2[i][j]) printf("%d --> %d, ", i, j);
	printf("\n");
}
void affg3(graphe3 g3){
	int i;
	liste p;
	for(i = 0; i < N; i++) for(p = g3[i]; p; p = p -> suite) printf("%d --> %d, ", i, p -> s);
	printf("\n");
}
void calculdistance(graphe3 g3, sommet depart, int d[N], sommet pere[N])
{ int t[N], i1=0, i2=0, i;
  liste p;
  for(i=0; i<N; i++) d[i]=pere[i]=N;
  d[pere[depart]=t[i2++]=depart]=0;
  while(i1<i2)
   for(p=g3[i=t[i1++]]; p; p=p->suite)
    if(d[p->s]==N)
     d[t[i2++]=p->s] = 1+d[pere[p->s]=i];
}
void affPlusCourtChemin(graphe3 g3, sommet depart, sommet arrivee)
{ int d[N], i, j;
  sommet pere[N], c[N];
  calculdistance(g3, depart, d, pere);
  if(pere[arrivee]==N) printf("Il n' y a pas de chemin de %d vers %d\n", depart, arrivee); else
  {	for(i=arrivee; c[d[i]]=i, i!=depart; i=pere[i]) ;
    for(j=0; j<d[arrivee]; j++) printf("%d-->", c[j]);
    printf("%d\n", arrivee);
  }
}
void affCycle(graphe3 g3)
{ int pere[N], i;
  sommet sp=N, ss=N;
  void parcours(sommet s, sommet papa)
  { if(pere[s]>N) ss=s, sp=papa;
    if(pere[s]!=N) return;
    pere[s]=N+1;
    liste p;
    for(p=g3[s]; p; p=p->suite) parcours(p->s, s);
    pere[s]=papa;
  }
  for(i=0; i<N; i++) pere[i]=N;
  for(i=0; i<N; i++) parcours(i, i);
  if(ss==N)	printf("Pas de cycle\n"); else
  { printf("Cycle existant : ");
    for(i=sp; i!=ss; i=pere[i])	printf("%d<--",i);
    printf("%d<--%d\n", ss, sp);
  }
}
void retourneg3(graphe3 g, graphe3 h)
{ int i, j;
  liste p, q;
  for(i=0; i<N; i++) h[i]=0;
  for(i=0; i<N; i++) for(p=g[i]; p; p = q)
  { j=p->s;
    p->s=i;
    q=p->suite;
    p->suite=h[j];
    h[j]=p;
  }
}
int rechercheCFC3(graphe3 g, int cfc[N])
{ int fin[N], ifin=0, nbcfc=0;
  graphe3 h;
  void parcours1(sommet s)
  { if(cfc[s]==N)
    { liste p;   
      cfc[s]=N+1;
      for(p=g[s]; p; p=p->suite) parcours1(p->s);
      fin[ifin++]=s;
    }
  }
  void parcours2(sommet s)
  { if(cfc[s]>N)
    { liste p;
      cfc[s]=nbcfc;
      for(p=h[s]; p; p=p->suite) parcours2(p->s);
    }
  }
  int i;
  for(i=0; i<N; i++) cfc[i]=N;
  for(i=0; i<N; i++) parcours1(i);
  retourneg3(g, h);
  while(ifin)	if(cfc[fin[--ifin]]>N) parcours2(fin[ifin]), nbcfc++;
  retourneg3(h, g);
  return nbcfc;
}
int rechercheCFC1(graphe1 g, int cfc[N])
{ int fin[N], ifin=0, nbcfc=0, tete[2*N], suite[2*A];
  void parcours1(sommet s)
  { if(cfc[s]==N)
    { int p;   
      cfc[s]=N+1;
      for(p=tete[2*s]; p>=0; p=suite[p]) parcours1(g[p+1]);
      fin[ifin++]=s;
    }
  }
  void parcours2(sommet s)
  { if(cfc[s]>N)
    { int p;
      cfc[s]=nbcfc;
      for(p=tete[2*s+1]; p>=0; p=suite[p]) parcours2(g[p-1]);
    }
  }
  int i, k;
  for(i=0; i<N; i++) cfc[i]=N, tete[i]=tete[i+N]=-1;
  for(k=0;k<2*A;k++) i=g[k]*2+(k&1), suite[k]=tete[i], tete[i]=k;
  for(i=0; i<N; i++) parcours1(i);
  while(ifin)	if(cfc[fin[--ifin]]>N) parcours2(fin[ifin]), nbcfc++;
  return nbcfc;
}
int main()
{ graphe1 h1,g1={0,2, 2,1, 1,3, 3,2, 1,0};
  graphe2 h2,g2={{0,0,1,0},{1,0,0,1},{0,1,0,0},{0,0,1,0}};
  struct maillon M02={2,0}, M21={1,0}, M13={3,0}, M32={2,0}, M10={0,&M13};
  graphe3 h3,g3={&M02, &M10, &M21, &M32};
  int cfc[N];

  printf("g1 : "), affg1(g1);
  printf("g2 : "), affg2(g2);
  printf("g3 : "), affg3(g3);
  printf("h3 : "), retourneg3(g3,h3), affg3(h3);
  printf("g3 : "), retourneg3(h3,g3), affg3(g3);
  printf("g1-->h3 : "), g1g3(g1, h3), affg3(h3);
  printf("g1-->h2 : "), g1g2(g1, h2), affg2(h2);
  printf("g2-->h3 : "), g2g3(g2, h3), affg3(h3);
  printf("g2-->h1 : "), g2g1(g2, h1), affg1(h1);
  printf("g3-->h1 : "), g3g1(g3, h1), affg1(h1);
  printf("g3-->h2 : "), g3g2(g3, h2), affg2(h2);
  printf("Il y a %d composantes fortement connexes :", rechercheCFC1(g1, cfc)), afft(cfc,N);
  printf("Il y a %d composantes fortement connexes :", rechercheCFC3(g3, cfc)), afft(cfc,N);
  affPlusCourtChemin(g3,0,3);
  affPlusCourtChemin(g3,3,0);
  affCycle(g3);
  	
  return 0;
}