#include<stdio.h>
#include<stdlib.h>
#define N 11
#define A (N==4?5:2*N)
typedef int graphe1[N][N], graphe3[2*A], tetesuite[N+2*A];
typedef struct maillon  maillon, *liste;    // maillon=srtuct maillon    liste=maillon*
struct maillon { int s; liste suite;};
typedef liste graphe2[N];

void afft(int *t, int n)
{ while(n--) printf("%d ",*t++);   // affiche les n premiers éléments du tableau t sur une même ligne
  printf("\n");                    // puis passe à la ligne
}

void affg1(graphe1 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 affg2(graphe2 g2)
{ int i;
  liste m;
  for(i=0;i<N;i++)
  for(m=g2[i];m;m=m->suite) printf("%d->%d ", i, m->s);
  printf("\n");
}
void affg3(graphe3 g3)
{ int k;
  for(k=0;k<2*A;k+=2) printf("%d->%d ", g3[k], g3[k+1]);
  printf("\n");
}

void g1g2(graphe1 g1, graphe2 g2)
{ int i,j;
  for(i=0;i<N;i++) g2[i]=0;
  for(i=0;i<N;i++)
  for(j=0;j<N;j++) if(g1[i][j])
  { liste m=malloc(sizeof(maillon));
    m->s=j;
    m->suite=g2[i], g2[i]=m;
  }
}
void g3g2(graphe3 g3, graphe2 g2)
{ int i,k;
  for(i=0; i<N; i++) g2[i]=0;
  for(k=0; k<2*A; k=k+2)
  { liste m = malloc(sizeof(maillon));
    m->s = g3[k+1];
    m->suite = g2[i=g3[k]], g2[i] = m;
  }
}
void g3g1(graphe3 g3, graphe1 g1)
{ int i,j,k;
  for(i=0;i<N;i++)
  for(j=0;j<N;j++) g1[i][j]=0;
  for(k=0;k<2*A;k=k+2) g1[g3[k]][g3[k+1]]=1;
}
void g2g1(graphe2 g2,graphe1 g1)
{ int i,j;
  liste m;
  for(i=0;i<N;i++)
  for(j=0;j<N;j++) g1[i][j]=0;
  for(i=0;i<N;i++)
  for(m=g2[i];m;m=m->suite) g1[i][m->s]=1;
}
void g2g3(graphe2 g2, graphe3 g3)
{ int k=0,i;
  liste m;
  for(i=0;i<N;i++)
  for(m=g2[i];m;m=m->suite)
   g3[k++]=i, g3[k++]=m->s;
}
void g1g3(graphe1 g1, graphe3 g3)
{ int k=0,i,j;
  for(i=0;i<N;i++)
  for(j=0;j<N;j++) if(g1[i][j])
   g3[k++]=i, g3[k++]=j;
}

void calcultetesuite(graphe3 g3, tetesuite tete)
{ int *suite=tete+N, i, k;
  for(i=0; i<N; i++) tete[i]=0;
  for(k=1; k<2*A; k+=2) suite[k]=tete[i=g3[k-1]], tete[i]=k;
}

int detecteCycle2(graphe2 g)
{ int etat[N], i, trouve=0;
  void visite(int s)
  { liste m;
    if(etat[s]==1) trouve=1;
    if(etat[s] || trouve) return;
    etat[s]=1;
    for(m=g[s]; m; m=m->suite) visite(m->s);
    etat[s]=2;
  }
  for(i=0; i<N; i++) etat[i]=0;
  for(i=0; i<N; i++) visite(i);
  return trouve;
}
int chercheCycle2( graphe2 g,int *cycle)
{ int chemin[N], profondeur[N], trouve=0, p=0;
  void visite(int s)
  { liste m;
    if(profondeur[s]>N || trouve) return;
    if(profondeur[s])
    { int i;
      for(i=profondeur[s]-1; i<p; i++) cycle[trouve++]=chemin[i];
      return;
    }
    chemin[p]=s;
    profondeur[s]=++p;
    for(m=g[s];m; m=m->suite) visite(m->s);
    profondeur[s]=N+1;
    p--;
  }
  int i;
  for(i=0; i<N; i++) profondeur[i]=0;
  for(i=0; i<N; i++) visite(i);
  return trouve;
}     

void retournegraphe1(graphe1 g1, graphe1 g2)
{ int i, j;
  for(i=0; i<N; i++)
  for(j=0; j<N; j++) g2[i][j]=g1[j][i];
}
void Retourne1(graphe1 g1)
{ int i,j;
  graphe1 g2;
  for(i=0; i<N; i++)
  for(j=0; j<N; j++) g2[i][j]=g1[j][i];
  for(i=0; i<N; i++)
  for(j=0; j<N; j++) g1[i][j]=g2[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)
{ graphe2 h2;
  int i,j;
  liste m,p;
  for(i=0;i<N;i++) h2[i]=g2[i], g2[i]=0;
  for(i=0;i<N;i++) for(p=h2[i];p;) m=p, p=m->suite, j=m->s, m->s=i, m->suite=g2[j], g2[j]=m;
}
void retourne3(graphe3 g3)
{ int i,k;
  for(k=0;k<2*A;k+=2) i=g3[k], g3[k]=g3[k+1], g3[k+1]=i;
}

int nbcfc1(graphe1 g1,int cfc[N])
{ int fin[N], ifin=0, nbcfc=0;
  void visite1(int s)
  { if(cfc[s]) return;
    cfc[s]=-1;
    int t;
    for(t=0;t<N;t++) if(g1[s][t]) visite1(t);
    cfc[s]=-2;
    fin[ifin++]=s;
  }
  void visite2(int s)
  { if(cfc[s]>-2) return;
    cfc[s]=-1;
    int t;
    for(t=0;t<N;t++) if(g1[t][s]) visite2(t);
    cfc[s]=nbcfc;
  }
  int i;
  for(i=0;i<N;i++) cfc[i]=0;
  for(i=0;i<N;i++) visite1(i);
  while(ifin) if(cfc[i=fin[--ifin]]<-1) visite2(i),nbcfc++;
  return nbcfc;
}
int nbcfc2(graphe2 g2,int cfc[N])
{ int fin[N], ifin=0, nbcfc=0;
  void visite1(int s)
  { if(cfc[s]) return;
    cfc[s]=-1;
    liste m;
    for(m=g2[s];m;m=m->suite) visite1(m->s);
    cfc[s]=-2;
    fin[ifin++]=s;
  }
  void visite2(int s)
  { if(cfc[s]>-2) return;
    cfc[s]=-1;
    liste m;
    for(m=g2[s];m;m=m->suite) visite2(m->s);
    cfc[s]=nbcfc;
  }
  int i;
  for(i=0;i<N;i++) cfc[i]=0;
  for(i=0;i<N;i++) visite1(i);
  retourne2(g2);
  while(ifin) if(cfc[i=fin[--ifin]]<-1) visite2(i),nbcfc++;
  retourne2(g2);
  return nbcfc;
}
int nbcfc3(graphe3 g3,int cfc[N])
{ tetesuite tete;
  int fin[N], ifin=0, nbcfc=0, *suite=tete+N;
  void visite1(int s)
  { if(cfc[s]) return;
    cfc[s]=-1;
    int k;
    for(k=tete[s];k;k=suite[k]) visite1(g3[k]);
    cfc[s]=-2;
    fin[ifin++]=s;
  }
  void visite2(int s)
  { if(cfc[s]>-2) return;
    cfc[s]=-1;
    int k;
    for(k=tete[s];k;k=suite[k]) visite2(g3[k]);
    cfc[s]=nbcfc;
  }
  int i;
  calcultetesuite(g3,tete);
  for(i=0;i<N;i++) cfc[i]=0;
  for(i=0;i<N;i++) visite1(i);
  retourne3(g3);
  calcultetesuite(g3,tete);
  while(ifin) if(cfc[i=fin[--ifin]]<-1) visite2(i),nbcfc++;
  retourne3(g3);
  return nbcfc;
}

int largeur1(graphe1 g1, int origine, int dist[N])
{ int i, j, nbIns=0, nbEnl=0, fil[N];
  for(i=0; i<N; i++) dist[i]=N;     // Aucun sommet n'est encore visité.
  dist[fil[nbIns++]=origine]=0;     // On met l'origine dans la file d'attente.
  while(nbIns!=nbEnl)               // Tant que la file n'est pas vide,
  { i=fil[nbEnl++];                 // on sort i de la file d'attente et
    for(j=0; j<N; j++)
    if(g1[i][j] && dist[j]==N)      // tout successeur de i non encore visité
     dist[fil[nbIns++]=j]=dist[i]+1;// est mis dans la file d'attente.
  }
  return nbIns;
}
int largeur2(graphe2 g2, int origine, int dist[N])
{ int j, i, nbIns=0, nbEnl=0, fil[N];
  liste m;
  for(i=0; i<N; i++) dist[i]=N;
  dist[fil[nbIns++]=origine]=0;
  while(nbIns!=nbEnl)
  for(m=g2[i=fil[nbEnl++]]; m; m=m->suite)
  if(dist[j=m->s]==N)
   dist[fil[nbIns++]=j]=dist[i]+1;
  return nbIns;
}
int largeur3(graphe3 g3, int origine, int dist[N])
{ tetesuite tete;
  int j, i, nbIns=0, nbEnl=0, fil[N], k, *suite=tete+N;
  calcultetesuite(g3,tete);
  for(i=0; i<N; i++) dist[i]=N;
  dist[fil[nbIns++]=origine]=0;
  while(nbIns!=nbEnl)
  for(k=tete[i=fil[nbEnl++]]; k; k=suite[k])
  if(dist[j=g3[k]]==N)
   dist[fil[nbIns++]=j]=dist[i]+1;
  return nbIns;
}

void retalea3(graphe3 g3,int x)
{ int k,s;
  for(k=0;k<2*A;k+=2) if(x=1234567*x+1,x&(1<<20)) s=g3[k],g3[k]=g3[k+1],g3[k+1]=s;
}
void echelle3(graphe3 g3)
{ int i,k=0;
  for(i=0;i<N;i++) g3[k++]=i, g3[k++]=(i+1)%N, g3[k++]=i, g3[k++]=(i+2)%N;
}  

int main()
{ maillon m1={1,0}, m2={2,0}, m3={2,&m1}, m4={3,0}, m5={0,0};
  graphe2 g2={&m3,&m2,&m4,&m5};
  graphe1 g1={{0,1,1,0},{0,0,1,0},{0,0,0,1},{1,0,0,0}};
  graphe3 g3={0,1, 1,2, 2,3, 0,2, 3,0};
  if(N>4) echelle3(g3), g3g1(g3,g1), g3g2(g3,g2);
  graphe1 h1, f1;
  graphe2 h2, f2;
  graphe3 h3, f3;
  printf("conversions de type\n");
  g1g2(g1,h2), g1g3(g1,f3), affg1(g1), affg2(h2), affg3(f3);
  g2g3(g2,h3), g2g1(g2,f1), affg2(g2), affg3(h3), affg1(f1);
  g3g1(g3,h1), g3g2(g3,f2), affg3(g3), affg1(h1), affg2(f2);
  printf("retournements de graphe\n");
  affg1(f1), retourne1(f1), affg1(f1), retourne1(f1), affg1(f1);
  affg2(f2), retourne2(f2), affg2(f2), retourne2(f2), affg2(f2);
  affg3(f3), retourne3(f3), affg3(f3), retourne3(f3), affg3(f3);
  int l, t[N], x;
  for(x=0;x<4;x++)
  { printf("\n");
    retalea3(g3,x), g3g2(g3,g2), g2g1(g2,g1), affg1(g1);
    printf("recherche de cycle\n");
    printf("%d %d : ",detecteCycle2(g2),l=chercheCycle2(g2,t)), afft(t,l);
    printf("tri topologique des composantes fortement connexes\n");
    printf("%d : ",nbcfc1(g1,t)), afft(t,N);
    printf("%d : ",nbcfc2(g2,t)), afft(t,N);
    printf("%d : ",nbcfc3(g3,t)), afft(t,N);
    printf("parcours en largeur d'abord\n");
    printf("%d : ",largeur1(g1,1,t)), afft(t,N);
    printf("%d : ",largeur2(g2,1,t)), afft(t,N);
    printf("%d : ",largeur3(g3,1,t)), afft(t,N);
  }
  return 0;
}