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

int A;
#define N 30000    // 100 ou 30000
#define A (4*N)

typedef char bool;       // 0 ou 1
typedef int sommet;      // 0 à N-1
#if N < 400
typedef bool gr1[N][N];
#else
typedef bool gr1[10][10];
#endif

typedef struct maillon maillon, *liste;
struct maillon { sommet s; liste suiv; };
typedef liste gr2[N];    //tableau de liste chaînée.

typedef struct {sommet ori,ext;} arc, gr3[A]; //définition des arcs, gr3 est un tableau d'arcs.
typedef int gr4[2*A], ts3[N+A], ts4[N+2*A];

#undef A

/*  Exemple des trois représentations d'un même graphe :
gr1 g1={{0,0,1,0},{1,0,1,0},{0,1,0,1},{0,1,0,0}};

maillon m6={1,0}, m5={3,0}, m4={1,&m5}, m3={2,0}, m2={0,&m3}, m1={2,0};
gr2 g2={&m1, &m2, &m4, &m6};

gr3 g3={{0,2},{2,3},{3,1},{1,2},{1,0},{2,1}};
*/

//Procédure pour créer un gr3 à partir d'un gr1
void gr1gr3(gr1 g1, gr3 g3)
{
  int i,j,k=0;
  for(i=0;i<N;i++)
   for(j=0;j<N;j++)
    if(g1[i][j])          //si l'arc  i-->j est dans le graphe g1
     g3[k++]=(arc){i,j};  //on le met dans g3
}


//Procédure pour créer un gr1 à partir d'un gr3
void gr3gr1(gr3 g3, gr1 g1)
{
  int i,j,k;
  for(i=0;i<N;i++)
   for(j=0;j<N;j++)
    g1[i][j]=0;     //on met tout g1 a 0.
  for(k=0;k<A;k++)
   g1[g3[k].ori][g3[k].ext]=1;    //on parcourt g3 pour créer g1.
}


//Procédure pour créer un gr3 à partir d'un gr2. Temps de calcul : A.
void gr2gr3(gr2 g2, gr3 g3)
{
  int i,k=0;
  liste p;
  for(i=0;i<N;i++)
   for(p=g2[i];p;p=p->suiv)
    g3[k++]=(arc){i,p->s};
}


//Procédure pour créer un gr1 à partir d'un gr2
void gr2gr1(gr2 g2, gr1 g1)
{
  int i,j;
  liste p;
  for(i=0;i<N;i++)
   for(j=0;j<N;j++)
    g1[i][j]=0;             // O(N²)
  for(i=0;i<N;i++)
   for(p=g2[i];p;p=p->suiv) // O(N+A)
    g1[i][p->s]=1;          // O(A)
}


liste nouv(int s,liste suiv)
{ liste a=malloc(sizeof(maillon));
  *a=(maillon){s,suiv};
  return a;
}

//Procédure pour créer un gr2 à partir d'un gr1
void gr1gr2(gr1 g1, gr2 g2)
{
  int i,j;
  for(i=0;i<N;i++)
  {
    liste l=0;
    for(j=0;j<N;j++)
     if(g1[i][j])   //s'il y a un arc de i vers j
      l=nouv(j,l);  // on ajoute j en tête de la liste des successeurs de i.
    g2[i]=l;
  }
}


//Procédure pour créer un gr2 à partir d'un gr3
void gr3gr2(gr3 g3, gr2 g2)
{
  int i,k;
  for(i=0;i<N;i++)
    g2[i]=0;
  for(k=0;k<A;k++)
    i=         g3[k].ori,
    g2[i]=nouv(g3[k].ext,g2[i]);
}


//Procédure pour désallouer un gr2.
void freegr2(gr2 g2)
{
  int i;
  liste s, suiv;
  for(i=0;i<N;i++)
   for(s=g2[i];s;s=suiv)
    suiv=s->suiv,
    free(s);
  for(i=0;i<N;i++) g2[i]=0;
}


//Procédures d'affichage
void Affgr1(gr1 g1)
{
  int i,j;
  for(i=0;i<N;i++)
   for(j=0;j<N;j++)
    if(g1[i][j])
     printf("%d -> %d  ", i, j);
  printf("\n");
}


void Affgr3(gr3 g3)
{
  int k;
  for(k=0;k<A;k++)
   printf("%d -> %d  ", g3[k].ori, g3[k].ext);
  printf("\n");
}


void Affgr2(gr2 g2)
{
  int i;
  liste s;
  for(i=0;i<N;i++)
   for(s=g2[i];s;s=s->suiv)
    printf("%d -> %d  ", i, s->s);
  printf("\n");
}





//TD 2 --------------------


//Chaînage des extrémités des arêtes correspondant à un même sommet.
void gr3ts(gr3 g3, ts3 tete)
{
  int i, j, *suiv=tete+N;
  for(i=0;i<N;i++) tete[i]=-1;
  for(j=0;j<A;j++) suiv[j]=tete[i=g3[j].ori], tete[i]=j;
}

void gr4ts(gr4 g4, ts4 tete, char sens)  // on chaîne les successeurs si sens='>'
{                                        //           les prédécesseurs si sens='<'
  int *suite=tete+N, i, j, j0;           // tous les voisins si sens vaut autre chose     
  for(i=0;i<N;i++)
   tete[i]=-1;
  for(j0=2;j0--;) if("<>"[j0]!=sens)
  for(j=j0;j<2*A;j+=2)
   suite[j]=tete[i=g4[j^1]],
   tete[i]=j;
}



//Procédure pour transposer la matrice d'adjacence g1.
void trans_g1(gr1 g1)
{
  int i,j,tmp;
  for(i=0;i<N;i++)
   for(j=0;j<i;j++)
   {
     tmp=g1[i][j];
     g1[i][j]=g1[j][i];
     g1[j][i]=tmp;
   }
}


//Procédure pour inverser le sens des arcs de g3.
void trans_g3(gr3 g3)
{
  int i,tmp;
  for(i=0;i<A;i++)
    {
      tmp=g3[i].ori;
      g3[i].ori=g3[i].ext;
      g3[i].ext=tmp;
    }
}


//Procédure pour inverser le sens des arcs de g2.
//Si on l'appelle deux fois de suite, on trie les arcs.
void trans_gr2(gr2 g2)
{
  int i,j;
  gr2 h2;
  liste p,q;

  for(i=0;i<N;i++) h2[i]=g2[i], g2[i]=0;
  for(i=0;i<N;i++)
    for(p=h2[i];p;)
      {
        q=p;
        p=q->suiv;
        j=q->s;  //L'arc de i vers j.
        q->s=i;  //l'extremite de l'arc = i.
        q->suiv=g2[j];
        g2[j]=q;
      }
}


void Aff_gr4(gr4 g4)
{
  int i;
  for(i=0;i<2*A;i=i+2)
   printf("%d<-->%d  ", g4[i],g4[i+1]);
}


// Les trois procédures suivantes sont des exemples d'obtention des
// successeurs d'un sommet donné selon la représentation des graphes utilisée.
// Elles sont a priori inutiles sauf peut-être pour le débogage.

void voisin_gr1(gr1 g1, sommet s)
{
  int i;
  printf("Les voisins de %d sont : ", s);
  for(i=0;i<N;i++)
   if(g1[s][i])
    printf("%d ", i);
  printf("\n");
}


void voisin_gr2(gr2 g2, sommet s)
{
  liste p;
  printf("Les voisins de %d sont : ", s);
  for(p=g2[s];p!=0;p=p->suiv)
   printf(" %d ",p->s);
  printf("\n");
}


void voisin_gr3(gr3 g3, ts3 tete, sommet s)
{
  int i, *suite=tete+N;
  printf("Les voisins de %d sont :", s);
  for(i=tete[s];i!=-1;i=suite[i])
   printf("%d ", g3[i].ext);
  printf("\n");
}

void voisin_gr4(gr4 g4, ts4 tete, sommet s)
{
  int i, *suite=tete+N;
  printf("Les voisins de %d sont : ", s);
  for(i=tete[s];i!=-1;i=suite[i])
   printf("%d ",g4[i]);
  printf("\n");
}




//TD 3 ------------------------------------------------------
// Les trois procédures suivantes montrent comment faire un parcours de
// graphe en largeur d'abord (Width First Search).
// Telles quelles, elles ne servent à rien. Mais en les modifiant un peu,
// on peut, par exemple, calculer le plus court chemin d'un sommet donné à
// chacun des autres.

int wfs2(gr2 g2,sommet depart,int file[N]) //width first search
{
  bool M[N];
  int io=0, jo=0;
  sommet x, y;
  liste p;

  for(x=0;x<N;x++) M[x]=0;

  M[file[jo++]=depart]=1; //   file[jo]=depart; M[depart]=1; jo++;
  //on met depart dans la file d'attente et on le marque
  while(io<jo)
   for(p=g2[x=file[io++]];p;p=p->suiv)
    if(!M[y=p->s])
     M[file[jo++]=y]=1;
  return jo;
  /*jo : nombre de sommets que l'on peut atteindre
    à partir de depart y compris lui même*/
}

int wfs3(gr3 g3, sommet depart, int file[N]) //width first search
{
  int tete[N+A], *suiv=tete+N;
  bool M[N];
  int io=0,jo=0;
  int x,y,k;
  gr3ts(g3,tete);

  for(x=0;x<N;x++) M[x]=0;

  M[file[jo++]=depart]=1;
  while(io<jo)
   for(k=tete[file[io++]];k>=0;k=suiv[k])
    if(!M[y=g3[k].ext])
     M[file[jo++]=y]=1;
  return jo;
}

int wfs1(gr1 g1,sommet depart,int file[N])//width first search
{
  bool M[N];
  int io=0, jo=0, j;

  for(j=0;j<N;j++) M[j]=0;

  M[file[jo++]=depart]=1;
  while(io<jo)
  {
    int x=file[io++], y;
    for(y=0;y<N;y++)
     if(g1[x][y] && !M[y])
       M[file[jo++]=y]=1;
  }
  return jo;
}

int distanceSommetgr3(gr3 g3, sommet depart, int d[N])
{
  int tete[N+A], *suiv=tete+N, x, y, k, file[N], io=0, jo=0;
  gr3ts(g3,tete);
 
  for(x=0;x<N;x++) d[x]=-1;
 
  d[file[jo++]=depart]=0; // on met départ dans la file d'attente et on le marque .
 
  while(io<jo)
   for(k=tete[x=file[io++]];k>=0;k=suiv[k])
    if(d[y=g3[k].ext]<0)
     d[file[jo++]=y]=d[x]+1;
 
  return io;
}

// Les trois procédures suivantes montrent comment faire un parcours de
// graphe en profondeur d'abord (Depth First Search).
// Telles quelles, elles ne servent pas à grand chose.
// Elles rendent l'arbre de parcours, dans le tableau pere :
// pere[i]=-1 si le sommet i n'est pas dans l'arbre (si on ne peut pas l'atteindre à partir
// de depart).
// pere[depart]=depart  La racine de l'arbre est le seul sommet de l'arbre sans père.
// Pour tout autre sommet i de l'arbre, pere[i] est le père du sommet i dans l'arbre. 
// Le parcours se fait par une procédure récursive «parcours» incluse dans une autre
// procédure. (C'est possible en C gnu comme en pascal)
// Le parcours pourrait se faire plus efficacement (2 à 10 fois vite et sans risque de
// débordement de la pile d'exécution) par une procédure itérative (et non pas récursive)
// voir la procédure nbcfc3 dans le TD suivant.

void Profondeurgr2(gr2 g2, int depart,int pere[N])
{
  void parcours(int s)
  {
   liste p;
   for(p=g2[s];p;p=p->suiv)
    if(pere[p->s]<0)
     pere[p->s]=s,
     parcours(p->s);
  }

  int j;
  for(j=0;j<N;j++) pere[j]=-1;
  pere[depart]=depart;
  parcours(depart);
}

void Profondeurg1(gr1 g1, int depart,int pere[N])
{
  void parcours(int s)
  {
    sommet t;
    for(t=0;t<N;t++)
     if(g1[s][t])
      if(pere[t]<0)
       pere[t]=s,
       parcours(t);
  }
  int j;
  for(j=0;j<N;j++) pere[j]=-1;
  pere[depart]=depart;
  parcours(depart);
}



//TD 4 ------------------------------------------------------

// Recherche des composantes fortement connexes d'un graphe orienté
// et tri topologique de ces composantes.
// Pour cela on parcourt deux fois le graphe.
//
// Le premier parcours doit être en profondeur d'abord. On prend les arcs en sens inverse.
// On note dans le tableau fin quand on a fini de visiter un sommet.
// Tout sommet non encore visité peut servir de point de départ pour le parcours en
// profondeur d'abord.
//
// Le deuxième parcours se fait dans l'autre sens (le sens direct). Il peut être en largeur
// ou en profondeur d'abord, peu importe. Le parcours utilisé ici est un hybride entre les
// deux. On utilise un tableau comme la file d'attente du parcours en largeur d'abord,
// mais en rentrant et en sortant les éléments du même coté. C'est donc une pile.
// Mais le parcours obtenu n'est pas en profondeur d'abord : On range dans la pile
// tous les frères en même temps comme s'il n'existait pas de chemins les reliant.
// Tout cela n'a pas d'importance : tous les sommets visités à partir d'un nouveau
// sommets sont de toute façon tous les sommets accessibles à partir du sommet de
// départ qui n'ont pas encore été visités.
// Ils forment une composante fortement connexe, à condition de prendre les sommets
// de départ dans l'ordre inverse de la fin de visite du premier parcours.

int nbcfc1(gr1 g1,int cfc[N])
{
  sommet a, b, c;
  int pile[N], nbPile=0, tete[N], fin[N], nbFin=0, nbCfc=-1;
  for(a=0;a<N;a++) cfc[a]=tete[a]=0; // Au début aucun sommet n'est marqué.
  for(a=0;a<N;a++)               // A partir de chaque sommet a
   if(cfc[a]) ; else             // non marqué,  on fait un parcours en profondeur d'abord :
    for(cfc[pile[nbPile++]=a]=-1;// On marque a en l'empilant,
        nbPile;)                 // puis tant que la pile n'est pas vide
     if(tete[b=pile[--nbPile]]==N) // on dépile un sommet b si la liste de ses
      fin[nbFin++]=b;              // prédécesseurs potentiels est épuisée.
     else
      if( nbPile++,               // Sinon on ne dépile pas b, mais 
          c=tete[b]++,            // on avance dans la liste de ses prédécesseurs potentiels.
          !cfc[c] && g1[c][b]     // Si c est un prédécesseur non marqué de b
        ) cfc[pile[nbPile++]=c]=-1; // on le marque en l'empilant
  while(nbFin)  // Chacun des sommets a pris dans l'ordre inverse de fin de visite lors
   if(cfc[a=fin[--nbFin]]<0)  // du premier parcours, s'il n'est pas encore visité,
    for(cfc[pile[nbPile++]=a]=++nbCfc; // est empilé et mis dans une nouvelle c.f.c.
        nbPile;)                       // Puis tant que la pile n'est pas vide,
     for(b=pile[--nbPile],c=0;c<N;c++) // on dépile un sommet b et chaque sommet c
      if(g1[b][c] && cfc[c]<0)         // successeur de b et non encore visité
       cfc[pile[nbPile++]=c]=nbCfc;    // est empilé et mis dans la même c.f.c.
  return nbCfc+1;  // nombre de c.f.c. On ajoute 1 pour compenser le -1 initial.  
}

// La procédure suivante fait le parcours itératif «hybride» décrit plus haut.
// Elle recherche tous les sommets accessibles à partir du sommet de départ et
// les met dans une nouvelle composante (de numéro ++nbc). Elle fait cela en prenant
// comme sommets de départ possibles dans l'ordre : fin[N-1], fin[N-2], ..., fin[0].
// Si fin est le pointeur nul, on fait comme si fin[i]=i.
// Cette procédure peut donc faire le deuxième parcours lors de la recherche des
// composantes fortement connexes d'un graphe orienté. Mais elle peut aussi chercher
// les composantes connexes d'un graphe non orienté (alors fin=0).  

int nbcc3(gr3 g3,int cc[N],int fin[N])
{ sommet s;
  int tete[N+A], *suiv=tete+N, pile[N], ip=0, nbc=-1, i, k;
  gr3ts(g3,tete);
  for(s=N;s--;) cc[s]=-1;
  for(i=N;i--;)   // Pour s=fin[N-1], fin[N-2], ..., fin[0] (ou N-1, N-2, ..., 0 si fin est nul)
   if(cc[s=fin?fin[i]:i]<0)  // si s n'est pas marqué,
    for(cc[pile[ip++]=s]=++nbc; // c'est le premier sommet d'une nouvelle composante.
        ip;)                 // On l'empile, puis tant que la pile n'est pas vide,
     for(k=tete[pile[--ip]];k>=0;k=suiv[k])// on dépile un sommet et tous ses successeurs 
      if(cc[s=g3[k].ext]<0)  // non encore visités
       cc[pile[ip++]=s]=nbc; // sont empilés et mis dans la même composante.
  return nbc+1;              // Nombre de composantes. On ajoute 1 pour compenser le -1 initial.  
}

int nbcfc3(gr3 g3,int cfc[N])
{ int fin[N];
  { sommet a, b, c;
    int pile[N], nbPile=0, nbFin=0, tete[N+A], *suiv=tete+N, k;
    trans_g3(g3); gr3ts(g3,tete); trans_g3(g3); // On fait les listes des prédécesseurs.
    for(a=0;a<N;a++) cfc[a]=0;     // Au début aucun sommet n'est marqué.
    for(a=0;a<N;a++)               // A partir de chaque sommet a
     if(cfc[a]) ; else             // non marqué,  on fait un parcours en profondeur d'abord :
      for(cfc[pile[nbPile++]=a]=-1;// On marque a en l'empilant,
          nbPile;)                 // puis tant que la pile n'est pas vide
       if(k=tete[b=pile[--nbPile]],k<0 ) // on dépile un sommet b si la liste de ses
        fin[nbFin++]=b;            // prédécesseurs est épuisée.
       else
        if( nbPile++,              // Sinon on ne dépile pas b, mais 
            tete[b]=suiv[k],       // on avance dans la liste de ses prédécesseurs .
            !cfc[c=g3[k].ori]      // Si c est un prédécesseur non marqué de b
          ) cfc[pile[nbPile++]=c]=-1; // on le marque en l'empilant
  }
  return nbcc3(g3,cfc,fin); // parcours en avant en partant de fin[N-1], fin[n-2], ... fin[0]
}

int nbcc4(gr4 g4,int cc[N],int fin[N])
{ sommet s;
  int tete[N+A+A], *suiv=tete+N, pile[N], ip=0, nbc=-1, i, k;
  gr4ts(g4,tete,fin?'>':'*');// On chaîne les voisins (si fin est nul) ou les successeurs de chaque sommet.
  for(s=N;s--;) cc[s]=-1;
  for(i=N;i--;)   // Pour s=fin[N-1], fin[N-2], ..., fin[0] (ou N-1, N-2, ..., 0 si fin est nul)
   if(cc[s=fin?fin[i]:i]<0)  // si s n'est pas marqué,
    for(cc[pile[ip++]=s]=++nbc; // c'est le premier sommet d'une nouvelle composante.
        ip;)                 // On l'empile, puis tant que la pile n'est pas vide,
     for(k=tete[pile[--ip]];k>=0;k=suiv[k])// on dépile un sommet et tous ses successeurs 
      if(cc[s=g4[k]]<0)      // non encore visités
       cc[pile[ip++]=s]=nbc; // sont empilés et mis dans la même composante.
  return nbc+1;              // Nombre de composantes. On ajoute 1 pour compenser le -1 initial.  
}

// graphe pseudo-aléatoire non orienté de grande taille
// i<-->j est une arête ssi i+j+i*j+i²j² est divisible par N.

void set1gr3(gr3 g3)   // procédure simple en temps O(N²)
{ int i,j,ij,k=0;
  for(i=0;i<N;i++) for(j=0;j<=i;j++) if(ij=i*j%N,(i+j+ij+ij*ij)%N==0)
  { if(        k++<A) g3[k-1]=(arc){i,j};
    if(i!=j && k++<A) g3[k-1]=(arc){j,i};
  }
  printf("A=%d k=%d\n",A,k);
  if(k!=A) exit(1);
}
int set2gr3(gr3 g3)   // procédure plus efficace en temps O(N)
{ int i,i2,j,ij,s,d,k=0,tete[N],suiv[N];
  for(i=0;i<N;i++) tete[i]=-1;
  for(j=0;j<N;j++) suiv[j]=tete[i=j*j%N], tete[i]=j;
  for(ij=0;ij<N;ij++)
  for(d=tete[s=ij*(N+~ij)%N,(s*s-4*ij+4*N)%N];d>=0;d=suiv[d])
  for(i2=(s+d)%N;i2<2*N;i2+=N) if(1&~i2) if(i=i2/2, j=(s-i+N)%N, i*j%N==ij)
  if(k++,g3) g3[k-1]=(arc){i,j};
  return k;
}

// modification d'un graphe orienté i-->j devient i-->(j+1)%N
void tordgr3(gr3 g3)
{ int k;
  for(k=0;k<N;k++) g3[k].ext=(g3[k].ext+1)%N;
}

void stat(int cc[N])
{ int card[N], eff[N+1], i;
  for(i=0;i<N;i++) card[i]=eff[i]=0;
  eff[N]=0;
  for(i=0;i<N;i++) card[cc[i]]++;  // card[i] est le nombre de sommets de la composante n° i
  for(i=0;i<N;i++) eff[card[i]]++; // eff[c] est le nombre de composantes de taille c
  for(i=1;i<=N;i++) if(eff[i]) printf(" %dx%d ",eff[i],i);
  printf("\n");
}

void statcfc(int cc[N],int cfc[N])
{ int nbcfc[N], vu[N], eff[N+1], i, c;
  for(i=0;i<N;i++) vu[i]=nbcfc[i]=eff[i]=0;
  eff[N]=0;
  for(i=0;i<N;i++) if(!vu[c=cfc[i]]) vu[c]=1, nbcfc[cc[i]]++;
  for(i=0;i<N;i++) eff[nbcfc[i]]++;
  for(i=1;i<=N;i++) if(eff[i]) printf(" %dx%d ",eff[i],i);
  printf("\n");
}

int main()
{
    arc g3[2*(A=set2gr3(0))];
    gr2 g2;
    int cc[N], cfc[N], k;

    set2gr3(g3);
    if(N<1000)
    {                 Affgr3(g3);
      gr3gr2(g3, g2); Affgr2(g2);
      gr2gr3(g2, g3); Affgr3(g3); freegr2(g2);
    }

    if(N<400)
    { gr1 g1;
      gr3gr1(g3, g1); Affgr1(g1);
      gr1gr3(g1, g3); Affgr3(g3);
      gr1gr2(g1, g2); Affgr2(g2);
      gr2gr1(g2, g1); Affgr1(g1); freegr2(g2);
    }
    printf("Le graphe non orienté a %d composantes connexes.\n",nbcc3(g3,cc,0));
    stat(cc);
    tordgr3(g3);
    printf("Le graphe orienté a %d composantes fortement connexes et"
           " %d composantes connexes.\n", nbcfc3(g3,cfc), nbcc4((sommet*)g3,cc,0));
    stat(cfc);
    stat(cc);

    // Autre façon de chercher les composantes connexes.
    for(k=A;k--;) g3[k+A]=(arc){g3[k].ext,g3[k].ori};
    A+=A;
    printf("Le graphe orienté a %d composantes connexes.\n", nbcc3(g3,cc,0));
    stat(cc);

    printf("Nombre de cfc des cc : ");
    statcfc(cc,cfc);
    
    return 0;
}