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

#if 0
  #define n 4
  #define a 5
#else
  #define n 11
  #define a 12
#endif

typedef int graphe1[n][n];
typedef int graphe2[2*a];
typedef struct maillon maillon, *liste;
struct maillon{int s; liste suite;};
typedef liste graphe3[n];

/*
void affg(graphe g)
{ int i,j;
  pour tout arc i-->j du graphe g
   printf("%d->%d ",i,j);
  printf("\n");
}
*/    

void affg1(graphe1 g1)
{ int i,j;
  for(i=0;i<n;i++)  //  pour tout sommet i
  for(j=0;j<n;j++)  //  pour tout sommet j
    if(g1[i][j])    //    s'il existe un arc i-->j
      printf("%d->%d ",i,j);
  printf("\n");
}

void affg2(graphe2 g2)    // les arcs sont g2[0]-->g2[1], g2[2]-->g2[3],  ...  g2[2*a-2]-->g2[2*a-1]
{ int k;
  for(k=0; k<2*a;k=k+2)              // pour k=0, 2, 4, ... 2*a-2 c'est-à-dire pour tout arc g2[k]-->g2[k+1]  
    printf("%d->%d ",g2[k],g2[k+1]);
  printf("\n");
}

void affg3(graphe3 g3)
{ int i;
  liste p;
  for(i=0;i<n;i++)             // pour tout sommet i
  for(p=g3[i];p;p=p->suite)    //   pour tout maillon *p de la liste chaînée g3[i], des successeurs de i. 
    printf("%d->%d ",i,p->s);
  printf("\n");
}

/*
void gxgy(graphex gx, graphey gy)  // gy=gx
{ gy=le graphe vide d'arc
  tout arc de gx
    est ajouté à gy
}
*/

void g1g2(graphe1 g1, graphe2 g2)
{ int i, j, k=0;     // le graphe g2 est initialement vide d'arc, car
  for(i=0;i<n;i++)   // k représente le nombre de sommets rangés dans le tableau g2, c'est-à-dire le double du nombre d'arcs.
  for(j=0;j<n;j++)
    if(g1[i][j])     // pour tout arc i-->j
      g2[k++]=i,     //   i et j sont ajoutés au bout du tableau g2
      g2[k++]=j;
}

void g2g1(graphe2 g2, graphe1 g1)
{ int i,j,k;
  for(i=0;i<n;i++)     // pour tout sommet i
  for(j=0;j<n;j++)     // pour tout sommet j
    g1[i][j]=0;        //   l'arc i-->j est noté absent du graphe g1
  for(k=0;k<2*a;k+=2)  // tout arc g2[k]-->g2[k+1] de g2
  g1[g2[k]][g2[k+1]]=1;//   est noté présent dans g1
}

void g1g3(graphe1 g1, graphe3 g3)
{ int i,j,k;
  for(k=0;k<n;k++)
  g3[k]=0;
  for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    if(g1[i][j])
    { liste p= malloc(sizeof(*p));
      p->s=j;
      p->suite=g3[i];
      g3[i]=p;
    }
}

void g3g1(graphe3 g3, graphe1 g1)
{ int i,j;
  liste p;
  for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    g1[i][j]=0;
  for(i=0;i<n;i++)
    for(p=g3[i];p;p=p->suite)
      g1[i][p->s]=1;
}

void g2g3(graphe2 g2, 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=g2[k], j=g2[k+1];
    liste p=malloc(sizeof(*p));
    p->s=j;
    p->suite=g3[i];
    g3[i]=p;
  }
}

void g3g2(graphe3 g3, graphe2 g2)
{ int i,k=0;
  liste p;
  for(i=0;i<n;i++)
  for(p=g3[i];p;p=p->suite)
    g2[k++]=i,
    g2[k++]=p->s;
}

void profondeur1(graphe1 g1,int pere[n], int depart)
{ void parcours(int i, int p)
  { int j;
    if(pere[i]>=0) return;
    pere[i]=p;
    for(j=0;j<n;j++) if(g1[i][j]) parcours(j,i);
  }
  int i;
  for(i=0;i<n;i++) pere[i]=-1;
  parcours(depart, depart);
}

void profondeur3(graphe3 g3, int pere[n],int depart)
{ void parcours(int i, int p)
  { liste q;
    if(pere[i]>=0) return;
    pere[i]=p;
    for(q=g3[i];q;q=q->suite) parcours(q->s,i);
  }
  int i;
  for(i=0;i<n;i++) pere[i]=-1;
  parcours(depart,depart);
}

void tete_suite(graphe2 g2, int tete[n+a])
{ int *suite=tete+n, i, k;
  for(i=0;i<n;i++) tete[i]=-1;
  for(k=0;k<a;k++) suite[k]=tete[i=g2[2*k]], tete[i]=k;
}

void profondeur2(graphe2 g2, int pere[n], int depart)
{ int tete[n+a],*suite=tete+n;
  void parcours(int i, int p)
  { int k;
    if(pere[i]>=0) return;
    pere[i]=p;
    for(k=tete[i];k!=-1;k=suite[k]) parcours(g2[2*k+1],i);
  }
  int i;
  tete_suite(g2,tete);
  for(i=0;i<n;i++) pere[i]=-1;
  parcours(depart, depart);
}

void aff(int tab[n])
{ int i;
  for(i=0;i<n;i++) printf("%2d ",tab[i]);
  printf("\n");
}

void largeur1(graphe1 g1, int pere[n], int depart)
{ int fi=0, fj=0, i, j, f[n];
  for(i=0;i<n;i++) pere[i]=-1;
  for(pere[f[fj++]=depart]=depart;fj>fi;)
    for(i=f[fi++],j=0;j<n;j++)
      if(g1[i][j])
        if(pere[j]<0)
          pere[f[fj++]=j]=i;
}

void largeur2(graphe2 g2, int pere[n], int depart)
{ int fi=0, fj=0, i, j, k, f[n], tete[n+a], *suite=tete+n;
  tete_suite(g2,tete);
  for(i=0;i<n;i++) pere[i]=-1;
  for(pere[f[fj++]=depart]=depart;fj>fi;)
    for(k=tete[i=f[fi++]];k>=0;k=suite[k])
      if(pere[j=g2[2*k+1]]<0)
        pere[f[fj++]=j]=i;
}

void largeur3(graphe3 g3, int pere[n], int depart)
{ int fi=0, fj=0, i, j, f[n];
  liste p;
  for(i=0;i<n;i++) pere[i]=-1;
  for(pere[f[fj++]=depart]=depart;fj>fi;)
    for(p=g3[i=f[fi++]];p;p=p->suite)
      if(pere[j=p->s]<0)
        pere[f[fj++]=j]=i;
}
void retourne1(graphe1 g1)
{ int i,j,x;
  for(i=0;i<n;i++)
  for(j=0;j<i;j++)
   x=g1[i][j], g1[i][j]=g1[j][i], g1[j][i]=x;
}

void retourne2(graphe2 g2)
{ int k,x;
  for(k=0;k<a;k++)
   x=g2[2*k], g2[2*k]=g2[2*k+1], g2[2*k+1]=x;
}

void retourne3(graphe3 g3)
{ graphe3 h3;
  liste p,q;
  int i,j;
  for(i=0;i<n;i++) h3[i]=g3[i], g3[i]=0;
  for(i=0;i<n;i++)
   for(p=h3[i];p;p=q)
    q=p->suite,
    j=p->s,
    p->s=i,
    p->suite=g3[j],
    g3[j]=p;
}

int nbcfc1(graphe1 g1, int cfc[n]) //nombre de composantes fortement connexes
{ int fin[n], h=0, nbcfc=0;
  void parcours1(int i)
  { if(cfc[i]) return;
    cfc[i]=-1;
    int j;
    for(j=0;j<n;j++) if(g1[i][j]) parcours1(j);
    fin[h++]=i;
  }
  void parcours2(int i)
  { if(cfc[i]>=0) return;
    cfc[i]=nbcfc;
    int j;
    for(j=0;j<n;j++) if(g1[j][i]) parcours2(j);
  }
  int i;
  for(i=0;i<n;i++) cfc[i]=0;
  for(i=0;i<n;i++) parcours1(i);
  while(h) if(cfc[i=fin[--h]]<0) parcours2(i), nbcfc++;
  return nbcfc;
}

int nbcfc2(graphe2 g2, int cfc[n])
{ int fin[n], h=0, nbcfc=0, tete[n+a], *suite=tete+n;
  void parcours1(int i)
  { if(cfc[i]) return;
    cfc[i]=-1;
    int k;
    for(k=tete[i];k>=0;k=suite[k])  parcours1(g2[2*k+1]);
    fin[h++]=i;
  }
  void parcours2(int i)
  { if(cfc[i]!=-1) return;
    cfc[i]=nbcfc;
    int k;
    for(k=tete[i];k>=0;k=suite[k]) parcours2(g2[2*k+1]);
  }
  tete_suite(g2,tete);
  int i;
  for(i=0;i<n;i++) cfc[i]=0;
  for(i=0;i<n;i++) parcours1(i);
  retourne2(g2);
  tete_suite(g2, tete);
  while(h) if(cfc[i=fin[--h]]<0) parcours2(i), nbcfc++;
  retourne2(g2);
  return nbcfc;
}

int nbcfc3(graphe3 g3, int cfc[n])
{ int fin[n], h=0, nbcfc=0;
  void parcours1(int i)
  { if(cfc[i]) return;
    cfc[i]=-1;
    liste p;
    for(p=g3[i];p;p=p->suite) parcours1(p->s);
    fin[h++]=i;
  }
  void parcours2(int i)
  { if(cfc[i]>=0) return;
    cfc[i]=nbcfc;
    liste p;
    for(p=g3[i];p;p=p->suite) parcours2(p->s);
  }
  int i;
  for(i=0;i<n;i++) cfc[i]=0;
  for(i=0;i<n;i++) parcours1(i);
  retourne3(g3);
  while(h) if(cfc[i=fin[--h]]<0) parcours2(i), nbcfc++;
  retourne3(g3);
  return nbcfc;
}

int main()
{ int pere[n], cfc[n];
#if n==4
  graphe1 g1={{0,0,0,1},
              {1,0,1,0},
              {0,0,0,1},
              {0,1,0,0}};
  graphe2 g2={0,3, 3,1, 1,2, 2,3, 1,0};
  maillon m1={3,0}, m2={1,0}, m3={2,0}, m4={3,0}, m5={0,&m3};
  graphe3 g3={&m1,&m5,&m4,&m2};
#else
  graphe2 g2={1,2, 1,3, 3,5, 5,6, 6,7, 5,7, 3,4, 5,4, 10,4, 8,10, 5,8, 8,9};
  graphe1 g1; g2g1(g2,g1);
  graphe3 g3; g2g3(g2,g3);
#endif
  graphe1 h1,f1;
  graphe2 h2,f2;
  graphe3 h3,f3;

  affg1(g1);
  affg2(g2);
  affg3(g3);

  printf("g1g2 "); g1g2(g1,h2); affg2(h2);
  printf("g2g1 "); g2g1(g2,h1); affg1(h1);
  printf("g1g3 "); g1g3(g1,h3); affg3(h3);
  printf("g3g1 "); g3g1(g3,f1); affg1(f1);
  printf("g2g3 "); g2g3(g2,f3); affg3(f3);
  printf("g3g2 "); g3g2(g3,f2); affg2(f2);
  profondeur1(g1,pere,n==4?0:5); aff(pere);
  profondeur3(g3,pere,n==4?0:5); aff(pere);
  profondeur2(g2,pere,n==4?0:5); aff(pere);
  largeur1   (g1,pere,n==4?0:5); aff(pere);
  largeur2   (g2,pere,n==4?0:5); aff(pere);
  largeur3   (g3,pere,n==4?0:5); aff(pere);
  printf("%d ", nbcfc1(g1,cfc)), aff(cfc);
  printf("%d ", nbcfc2(g2,cfc)), aff(cfc);
  printf("%d ", nbcfc3(g3,cfc)), aff(cfc);
  return 0;
}