#include<stdio.h>
#include<stdlib.h>
typedef enum {A,B,C,D,E,F,G,H} sommet;
typedef enum {faux,vrai} bool;
#define NBS 1000 // nombre de sommets du graphe
#define NBA 2000 // nombre d'arcs du graphe
typedef bool G1[NBS][NBS];
void affsom(int i)
{ if(i>=26) affsom(i/26);
  printf("%c",'A'+i%26);
}
void affarc(int i,int j)
{ affsom(i),printf("->"),affsom(j),printf(" "); }
void affG1(G1 g)
{ sommet i,j;
  for(i=0;i<NBS;i++)
  for(j=0;j<NBS;j++) if(g[i][j])
  affarc(i,j);
  printf("\n");
} 
typedef struct{int degre; sommet*succ;} G2[NBS];
void affG2(G2 g)
{ sommet i,j;
  for(i=0;i<NBS;i++)
  for(j=0;j<g[i].degre;j++)
  affarc(i,g[i].succ[j]);
  printf("\n");
}
typedef sommet G3[2*NBA];
void affG3(G3 g)
{ int k;
  for(k=0;k<2*NBA;k+=2) affarc(g[k],g[k+1]);
  printf("\n");
}
void G3G1(G3 g3,G1 g1)
{ int i,j,k;
  for(i=0;i<NBS;i++)
  for(j=0;j<NBS;j++) g1[i][j]=faux;
  for(k=0;k<2*NBA;k+=2) g1[g3[k]][g3[k+1]]=vrai;
}
void G1G3(G1 g1,G3 g3)
{ sommet i,j;
  for(i=0;i<NBS;i++)
  for(j=0;j<NBS;j++) if(g1[i][j]) *g3++=i, *g3++=j;
}
void G3G2(G3 g3,G2 g2, sommet su[],int dk)
// dk=2 graphe orienté  dk=1 graphe non orienté
{ sommet i;
  int k;
  for(i=0;i<NBS;i++) g2[i].degre=0;
  for(k=0;k<2*NBA;k+=dk) g2[g3[k]].degre++;
//for(i=0;i<NBS;i++) g2[i].succ=su,su+=g2[i].degre,g2[i].degre=0;
//for(k=0;k<2*NBA;k+=2) g2[g3[k]].succ[g2[k].degre++]=g3[k+1];
  for(i=0;i<NBS;i++) g2[i].succ=su+=g2[i].degre;
  for(k=0;k<2*NBA;k+=dk) *--g2[g3[k]].succ=g3[k^1];
}
void G2G3(G2 g2,G3 g3)
{ sommet i; int k;
  for(i=0;i<NBS;i++) for(k=0;k<g2[i].degre;k++)
  *g3++=i, *g3++=g2[i].succ[k];
}
void G1G2(G1 g,G2 h,sommet*su)
{ sommet i,j;
  for(i=0;i<NBS;i++)
  { h[i].degre=0; h[i].succ=su;
    for(j=0;j<NBS;j++) if(g[i][j]) h[i].degre++, *su++=j;
  }
}
/* Parcours en profondeur d'abord (Depth First Search)
  DFS(sommet a)
    pour chacun des voisins b de a non encore visités faire
  	  DFS(b)
    fait
*/
int nbcc(G2 g, int cc[])
{ int nbc=0;
  void dfs(sommet a)
  { cc[a]=nbc; // On note que le sommet a est visité
    int k;
    for(k=0;k<g[a].degre;k++)
    { sommet b=g[a].succ[k];
      if(cc[b]<0) dfs(b);  // si b n'a pas encore été visité
    }
  }
  sommet a;
  for(a=0;a<NBS;a++) cc[a]=-1; // Aucun sommet n'a été visité
  for(a=0;a<NBS;a++) if(cc[a]<0) dfs(a), nbc++;
  return nbc;
}
/* recherche des composantes fortement connexes :
  On fait un parcours en profondeur d'abord, mais :
  1) On numérote les sommets dans l'ordre où on les atteint.
  2) On maintient pour chaque sommet le plus petit numéro
     des sommets qu'il peut atteindre.
  3) On empile les sommets quand on les atteint.
  4) Quand on a fini d'explorer un sommet et tous ses
     successeurs, si le plus petit numéro de sommet
     accessible est le numéro du sommet courant, alors
     on dépile tous les sommets jusqu'au sommet courant.
     Les sommets dépilés forment une composante fortement connexe.
  5) cfc[a] et min[a] contiennent :
     une valeur indéfinie et -1 tant que sommet a n'a pas été visité, puis
     le numéro du sommet et le plus petit numéro accessible
       tant que le sommet est dans la pile, et enfin
     le numéro de sa composante fortement connexe et NBS.
*/
int nbcfc(G2 g, int cfc[])
{ int pile[NBS], *p=pile, num=0, nbc=0, min[NBS];
  void dfs(sommet a)
  { cfc[*p++=a]=min[a]=num++;//On attribue un numéro à a et on l'empile
    int k, b;
    for(k=0;k<g[a].degre;k++)
    { b=g[a].succ[k];
      if(min[b]<0) dfs(b);  // si b n'a pas encore été visité
      if(min[b]<min[a]) min[a]=min[b];
    }
    if(cfc[a]!=min[a]) return;
    do cfc[b=*--p]=nbc, min[b]=NBS; while(b!=a);
    nbc++;
  }
  sommet a;
  for(a=0;a<NBS;a++) min[a]=-1; // Aucun sommet n'a été visité
  for(a=0;a<NBS;a++) if(min[a]<0) dfs(a);
  return nbc;
}
void G3aleat(G3 g)
{ int i;
  for(i=0;i<2*NBA;i++) g[i]=rand()%NBS;
}
void affboucle(G2 g,int cc[])
{ sommet s[NBS], vu[NBS];
  int a,k,b;
  for(a=0;a<NBS;a++)
  { s[a]=a, vu[a]=0;
    for(k=0;k<g[a].degre && s[a]==a;k++)
    if(cc[b=g[a].succ[k]]==cc[a]) s[a]=b;
  }
  for(a=0;a<NBS && s[a]==a;a++) ;
  if(a==NBS) {printf("pas de boucle\n"); return; }
  do vu[a]=1, a=s[a]; while(!vu[a]);
  b=a;
  do printf("%d->",a), a=s[a]; while(a!=b);
  printf("%d\n",a);
}
void afft(int *t,int n)
{ while(n--) printf("%d ",*t++);
  printf("\n");
}
int main()
{ G2 h2;
  G3 g3;
  sommet su2[NBA*2];
#if NBS==8 && NBA==7
  sommet i,j;
  G1 g1;
  G2 g2;
  for(i=0;i<NBS;i++)
  for(j=0;j<NBS;j++) g1[i][j]=faux;
  g1[A][B]=vrai;
  g1[B][D]=vrai;
  g1[D][C]=vrai;
  g1[C][A]=vrai;
  g1[C][D]=vrai;
  g1[D][B]=vrai;
  g1[E][F]=vrai;
  affG1(g1);
  g2[A].degre=1;
  g2[B].degre=1;
  g2[C].degre=2;
  g2[D].degre=2;
  g2[E].degre=1;
  g2[F].degre=0;
  g2[G].degre=0;
  g2[H].degre=0;
  for(i=0;i<NBS;i++)
   g2[i].succ=malloc(g2[i].degre*sizeof(*g2[i].succ));
  g2[A].succ[0]=B;
  g2[B].succ[0]=D;
  g2[C].succ[0]=A;
  g2[C].succ[1]=D;
  g2[D].succ[0]=C;
  g2[D].succ[1]=B;
  g2[E].succ[0]=F;
  affG2(g2);
  sommet su[NBA]={B,D,A,D,C,B,F};
  G2 f2={{1,su},{1,su+1},{2,su+2},{2,su+4},{1,su+6},{0},{0},{0}};
  affG2(f2);
  G1G2(g1,h2,su2);
  affG2(h2);
  G1G3(g1,g3);
  affG3(g3);
#endif
  G3aleat(g3);
  int cc[NBS];
  G3G2(g3,h2,su2,1); affG2(h2); // graphe non orienté
  printf("Il y a %d composantes connexes.\n",nbcc(h2,cc));
  afft(cc,NBS);
  G3G2(g3,h2,su2,2); affG2(h2); // graphe orienté
  printf("Il y a %d composantes fortement connexes.\n",nbcfc(h2,cc));
  afft(cc,NBS);
  affboucle(h2,cc);
  return 0;
}