//  gcc graphe.c -std=gnu99 -Wall
#include<stdio.h>
#define NVMAX 1000
#define NEMAX 10000
/* 
Si un graphe à nv sommets, ils sont numérotés de 0 à nv-1, pour pouvoir les utiliser comme indice dans un tableau.
NVMAX est un majorant du nombre de sommets qui peut servir de dimension par défaut pour un tel tableau (qui sera donc surdimentionné).
De même on définit NEMAX un majorant du nombre ne d'arêtes ou d'arcs.
Puisque les sommets sont numérotés de 0 à nv-1, l'ensemble des sommets est entièrement déterminé par leur nombre nv.
L'ensemble des arêtes ou des arcs peut être représenté de diverses façons.
Pour chacune d'elle on doit pouvoir traduire efficacement la boucle :
 pour chaque sommet t successeur de s faire truc(t)
Dans cette boucle, le nombre d'appel à truc() est égal au nombre de successeurs t de s. C'est le nombre d'arcs sortant du sommet s,
qu'on appelle le degré sortant de s. Pour que la gestion de la boucle prenne un temps proportionnel à ce nombre,
il faut avoir la liste des successeurs de chacun des sommets.
Si la boucle est dans une procédure qui est exécutée une fois pour chacun des sommets s, alors le nombre total d'appels à truc()
sera la somme des degrés sortant de tous les sommets, c'est-à-dire le nombre d'arcs ne.
*************************************************Graphe dense*************************************************
Si le graphe est dense, c'est-à-dire si ne n'est pas négligeable devant nv*nv, on peut se passer de stocker les listes d'adjacences
pour chaque sommet et utiliser à la place une matrice d'adjacence :
g[i][j] est un booléen indiquant s'il existe un arc de i vers j.
  for(int t=nv;t--;) if(g[s][t]) truc(t);
*/
typedef int graphe_dense[][NVMAX], tnv[NVMAX];

enum {A,B,C,D,E}; //à peu près équivalent à   const int A=0, B=1, C=2, D=3, E=4;
graphe_dense
 g1={{0,1,1,0,0}, //Successeurs de A       A---B  
     {1,0,1,0,0}, //Successeurs de B        \ /
     {1,1,0,0,0}, //Successeurs de C         C
     {0,0,0,0,1}, //Successeurs de D            D---E
     {0,0,0,1,0}  //Successeurs de E
    },
 h1={{0,1,0,1,0}, // A->B, A->D          A------>B
     {0,0,1,0,0}, // B->C                |\__ __/|
     {0,0,0,1,0}, // C->D                | __E   |
     {0,0,0,0,1}, // D->E                v/      v
     {1,1,0,0,0}  // E->A, E->B          D<------C
    };
//Parcours en profondeur d'abord pour un graphe dense représenté par une matrice d'adjacence.
int nbatteint1(graphe_dense g, int nv, int s) //Compte les sommets qu'on peut atteindre en avant à partir du sommet s.
{ int vu[nv], cpt=0;                  // cpt est le nombre de sommets visités.
  void dfs(int s)
  { vu[s]=1; cpt++;                   // On note que le sommet s a été visité
    for(int t=0; t<nv; t++)           // Puis chaque sommet t successeur de s qui
     if(g[s][t] && !vu[t]) dfs(t);    //  n'a pas encore été visité est visité
  }
  for(int i=0; i<nv; i++) vu[i]=0;    // Au début aucun sommet n'a encore été visité.
  dfs(s);                             // On visite s et tous ses successeurs et leurs successeurs etc.
  return cpt;
}
/* Si un graphe est clairsemé, une matrice d'adjacence prend trop de place, et trop de temps à lire.
On peut faire une liste des arêtes et/ou pour chaque sommet une liste de ses successeurs.
Une liste peut être mise dans un tableau, ou elle peut être chaînée avec des pointeurs ou des tableaux.
************************************************************Graphe chaine**************************************************************
g[s] représente la liste chaînée des sommets adjacents à s
  for(liste p=g[s];p;p=p->next) truc(p->s);
*/
typedef struct maillon maillon, *liste;
struct maillon {int s; liste next;};
typedef liste graphe_chaine[NVMAX];

maillon m1={C,0}, m2={B,&m1},  m3={A,&m1},  m4={A,0}, m5={B,&m4},  m6={E,0},  m7={D,0},  m8={B,&m7};
graphe_chaine g2={&m2,&m3,&m5,&m6,&m7}, h2={&m8,&m1,&m7,&m6,&m5};

int nbatteint2(graphe_chaine g, int nv, int s)
{ int vu[nv], cpt=0;                  // cpt est le nombre de sommets visités.
  void dfs(int s)                                                                                      
  { vu[s] = 1; cpt++;                 // On note que le sommet s a été visité
    for(liste p=g[s]; p; p=p->next)   // Puis chaque sommet p->s successeur de s qui
     if(!vu[p->s]) dfs(p->s);         //  n'a pas encore été visité est visité
  }                                                                                                    
  for(int i=0; i<nv; i++) vu[i]=0;    // Au début aucun sommet n'a encore été visité.
  dfs(s);                             // On visite s et tous ses successeurs et leurs successeurs etc.
  return cpt;
}
/************************************************************Graphe succ****************************************************************
On peut mettre la liste des successeurs de chacun des sommets dans un tableau et mettre tous ces tableaux bout à bout dans un grand tableau.
Il faut donc garder aussi les limites de ces listes dans un autre tableau :
int lim[nv+1]={0,2,4,6,7,8}, succ[ne]={B,C,  A,C,  A,B,  E,  D};
Donc lim[0]=0, lim[nv]=ne et  lim[s+1]-lim[s]=degre_sortant(s)
  for(i=lim[s];j<lim[s+1],j++) truc(succ[j]);
On peut mettre bout à bout les deux tableaux lim et succ dans un grand tableau de taille nv+ne+1. */
typedef int graphe_succ[NVMAX+NEMAX+1];

graphe_succ g3={0,2,4,6,7,8,  B,C,  A,C,  A,B,  E,  D}, h3={0,2,3,4,5,7,  B,D,  C,  D,  E,  A,B};

int nbatteint3(graphe_succ lim, int nv, int s)
{ int *succ=nv+1+lim, vu[nv], cpt=0;        // cpt est le nombre de sommets visités.
  void dfs(int s)                                                                                            
  { vu[s] = 1; cpt++;                       // On note que le sommet s a été visité
    for(int i=lim[s]; i<lim[s+1] ; i++)     // Puis chaque sommet succ[i] successeur de s qui
     if(!vu[succ[i]]) dfs(succ[i]);         //  n'a pas encore été visité est visité
  }                                                                                                          
  for(int i=0; i<nv; i++) vu[i]=0;          // Au début aucun sommet n'a encore été visité.
  dfs(s);                                   // On visite s et tous ses successeurs et leurs successeurs etc.
  return cpt;
}

/************************************************************Graphe arcs****************************************************************
La méthode la plus simple est de placer les extrémités des arcs bout à bout dans un tableau de taille 2ne. */
typedef int graphe_arcs[2*NEMAX];

graphe_arcs g4={A,B,  A,C,  B,C,  B,A,  E,D,  C,B,  D,E,  C,A}, h4={A,B,  B,C,  C,D,  D,E,  E,A,  A,D,  E,B};
/* Les arcs sont h3[2*i]->h3[2*i+1] pour i=0...ne-1.
On peut fabriquer des listes d'adjacence chaînées avec des tableaux.
  for(int k=tete[s];k>=0;k=suite[k]) truc(g[k]);
int g[]    ={A,B,  B,C,   A,D,   C,A,   D,E,    B,A};
             0,1,  2, 3,  4, 5,  6, 7,  8, 9,  10,11
int suite[]={ ,5,   ,11,   ,-1,   ,-1,   ,-1,    ,-1}; //-1 = fin de la liste des successeurs
int tete[]={1, 3, 7, 9, -1};
            A  B  C  D   E
On peut mettre les deux tableaux tete[nv] et suite[2*ne] bout à bout pour former un tableau tetesuite[nv+2*ne].
La procédure settetesuite() remplit ces tableaux à partir de la liste des arcs g[2*ne].
Le paramètre oriente est un booléen qui indique si le graphe est orienté.
Si oriente=1 (vrai), l'arc g[4]->g[5] se traduit en mettant 5 dans la liste des successeurs de g[4].
Si oriente=0 (faux), l'arête g[4]--g[5] se comporte comme les 2 arcs g[4]->g[5] et g[5]->g[4], donc
5 est mis dans la liste des successeurs de g[4] et 4 est mis dans la liste des successeurs de g[5].
Comme 4^1=5 et 5^1=4, en fait on met i^1 dans la liste des successeurs de g[i] pour les i pairs
quand le graphe est oriente et tous les i (pairs ou impairs) quand le graphe n'est pas orienté.
*/
typedef int tetesuite[NVMAX+NEMAX*2];
void settetesuite(graphe_arcs g, int nv, int ne, int oriente, tetesuite ts)
{ int *tete = ts, *suite = ts+nv, i;
  for(i=0; i<nv; i++) tete[i] = -1;  // les listes sont toutes initialement vides.
  for(i=0; i<2*ne; i+=1+oriente)     //On parcourt la liste des arcs g[i]->g[i^1] par pas de 1 ou 2.
   suite[i^1] = tete[g[i]], tete[g[i]] = i^1; //On ajoute i+1 (pour i pair) ou i-1 (pour i impair si !oriente) en tête de la liste numéro g[i]
}
#define TETESUITE(oriente) int ts[nv+2*ne], *tete=ts, *suite=ts+nv; settetesuite(g,nv,ne,oriente,ts);
int nbatteint4(graphe_arcs g, int nv, int ne, int oriente, int s)
{ TETESUITE(oriente)
  int vu[nv], cpt=0;                       // cpt est le nombre de sommets visités.
  void dfs(int s)                                                                                           
  { vu[s] = 1; cpt++;                      // On note que le sommet s a été visité
    for(int k=tete[s]; k!=-1 ; k=suite[k]) // Puis chaque sommet g[k] successeur de s qui
     if(!vu[g[k]]) dfs(g[k]);              //  n'a pas encore été visité est visité
  }                                                                                                         
  for(int i=0; i<nv; i++) vu[i]=0;         // Au début aucun sommet n'a encore été visité.
  dfs(s);                                  // On visite s et tous ses successeurs et leurs successeurs etc.
  return cpt;
}
void affiche_tab(int* tab, int n)  // affiche un tableau de n entiers, en les regroupant 2 par 2.
{ for(int i=0; i<n; i++) printf("%*d",7-(i&1),tab[i]);
  printf("\n");
}
#define Affiche_tab(tab,n) printf(#tab"="),affiche_tab(tab,n)
//*********************************génération de praphes***************************
int pforme=0;
// Dessin du graphe sous forme de grille en remplaçant les arcs par les 2 nombres qui les représentent.
void (*graphe_aff)(graphe_arcs,int*)=0;
void   grille_aff (graphe_arcs,int*);
void     tore_aff (graphe_arcs,int*);
/* grille(4,3,&nv,&ne,g) fait nv=12, ne=17 et met dans g[] les 17 arcs du graphe :
 0 <- 1 <- 2 <- 3
 ^    ^    ^    ^
 |    |    |    |
 4 <- 5 <- 6 <- 7
 ^    ^    ^    ^
 |    |    |    |
 8 <- 9 <-10 <-11  */
void grille(int largeur, int hauteur, int *nv, int *ne, graphe_arcs g)
{ pforme=largeur*256+hauteur, graphe_aff=grille_aff;
  printf("\ngrille %dx%d\n",largeur,hauteur);
  int i, j ,k=0;
  for(i=0; i<hauteur; i++)
  for(j=0; j<largeur; j++,k++)
  { if(j) *g++=k, *g++=k-1;        // arc vers la gauche
    if(i) *g++=k, *g++=k-largeur;  // arc vers le haut
  }
  *nv = k;
  *ne = k*2-largeur-hauteur;
}
void affgh(int*g, int*h, int i, char*t)
{ int a=g[i], b=g[i^1], c=h[i], d=h[i^1];
  if(a+b==c+d && (a==c || a==d)) printf("%6c",t[a!=c]); else  if(a) printf("%6d",a); else printf("%6s",".");
}
void grille_aff(graphe_arcs g, int dist[])  // dessine la grille fabriquée par grille(),
// en remplaçant éventuellement les flèches par les nombres contenus dans g[],
// et les numéros de sommets par les nombres contenus dans dist[].
{ const int largeur=pforme>>8, hauteur=pforme&255;
  graphe_arcs gg;
  int i, j ,k=0, jj, l, *G=gg;
  grille(largeur,hauteur,&i,&j,G);
  for(i=0; printf("\n"),i<hauteur; i++)
  for(j=0;              j<largeur; j++,k++)
  { if(i && !j)
//  for(l=2;l--;printf("\n")) for(jj=0;jj<largeur;jj++) printf("%6d%12s",g[4*jj+l],"");
    for(l=2;l--;printf("\n")) for(jj=0;jj<largeur;jj++) affgh(g,G,4*jj+l,l?"^|":"|v"), printf("%12s","");
//  if(j) l=*g++, printf("%6d%6d",*g++,l);
    if(j) affgh(g,G,0,"<-"),affgh(g,G,1,"->"),g+=2,G+=2;
    if(i) g+=2, G+=2;
    printf("%6d",dist?dist[k]:k);
  }
}
// Dans l'hypercube de dimension 5, les sommets 27=0b11011 et 19=0b10011 sont voisins
// car ils diffèrent d'un seul bit : 27^19=0b01000=8 est une puissance de 2.
void hypercube(int d, int* nv, int* ne, graphe_arcs g)
{ pforme=d, graphe_aff=0;
  printf("\nhypercube dim=%d\n",d);
  *nv=1<<d, *ne=d<<(d-1); // L'hypercube de dimension 5 a 2x2x2x2x2=32 sommets et 32*5/2=80 arêtes
  for(int e=1;e<*nv;e+=e) // pour e=1, 2, 4, 8, 16 faire
  for(int s=e;s<*nv;s++)  //   pour tout sommet s tel que s&e==e faire
  *g++=s|=e, *g++=s-e;    //      on ajoute l'arc s->s-e
}
/* Le graphe construit par tore(12,4,g) est :
     0<- 1<- 2<- 3<- 4  C'est une grille rectangulaire mais le bord droit
     |   |   |   |   |  est identifié au bord gauche et le bas est identifié au haut.
     v   v   v   v   v  C'est donc un tore.
     8<- 9<-10<-11<- 0
     |   |   |   |   |
     v   v   v   v   v
     4<- 5<- 6<- 7<- 8
     |   |   |   |   |
     v   v   v   v   v
     0<- 1<- 2<- 3<- 4  */
int tore(int nv, int h, graphe_arcs g)
{ pforme=nv*256+h, graphe_aff=tore_aff;
  printf("\ntore : %d sommets largeur=%d\n",nv,h);
  for(int i=0;i<nv;i++) *g++=i, *g++=i?i-1:nv-1, *g++=i, *g++=i<h?i-h+nv:i-h;  // i->i-1  i->i-h  (mod nv)
  return 2*nv;
}
void tore_aff(graphe_arcs g, int dist[])   // affiche le tore créé par tore()
{ const int nv=pforme>>8, h=pforme&255;
  int i, j ,k, l, G[4*nv];
  tore(nv,h,G);
  for(i=0; printf("\n"),i<nv ;)
  { k=i+h<nv?i+h:nv;
//  for(l=2;l--;printf("\n")) for(printf("%*s",12,""),j=i;j<k;j++) printf("%6d%12s",g[4*j+l+2],"");
    for(l=2;l--;printf("\n")) for(printf("%*s",12,""),j=i;j<k;j++) affgh(g,G,4*j+l+2,l?"^|":"|v"), printf("%12s","");
//  for(;i<k;i++) printf("%6d%6d%6d",g[4*i+1],g[4*i],dist?dist[i]:i);
    for(;i<k;i++) affgh(g,G,4*i+1,"<-"), affgh(g,G,4*i,"->"), printf("%6d",dist?dist[i]:i);
  }
}
void flip_arcs(graphe_arcs g, int ne, int z)  // Retourne pseudoaléatoirement les arcs du graphe g.
{ for(int k=0;k<2*ne;k+=2) if(z=12345*z+1,z<0) {int x=g[k]; g[k]=g[k+1], g[k+1]=x; } }
void graphe_dense_aleat(int nv, int ne, graphe_dense m, int z)
{ int i, j;
  for(i=nv;i--;) for(j=nv;j--;) m[i][j]=0;
  while(ne) 
  { do z=z*12345+1, i=z%(nv|1u); while(i>=nv);  // i est tiré au hasard entre 0 et nv-1
    do z=z*12345+1, j=z%(nv|1u); while(j>=nv);  // j aussi
    ne-=!m[i][j], m[i][j]=1;                    // On met un arc i->j que l'on compte s'il est nouveau
  }
}
void poids_arcs_aleat(graphe_arcs g, int ne, int z)
{ for(int k=0;k<2*ne;g[k++]=0, g[k++]=z%(ne|1u)+1) z=12345*z+1; }
//*********************** changement de représentation d'un graphe ********************************
void graphe_arcs_chaine(graphe_arcs g, int nv, int ne, graphe_chaine h, int oriente, maillon t[])
// Les maillons utilisés pour construire les listes chaînées ne sont pas alloués un par un par malloc(), ce qui serait très
// coûteux en temps et en place mais pris dans le tableau t passé en argument, qui peut avoir été alloué par un seul malloc()
// ou être un tableau local à la procédure appelant graphe_arc_chaine() et qui sera donc désalloué automatiquement à la fin
// de cette procédure. En fait ce programme ne contient ni malloc() ni free() ni #include<stdlib.h>
{ int i, k;
  for(i=0; i<nv; i++) h[i]=0;       // la liste h[i] des successeurs de i est initialement vide
  for(k=0; k<2*ne; k+=1+oriente)    // Pour chaque arc (i=g[k])->g[k^1]
    t->s=g[k^1], t->next = h[i=g[k]], h[i]=t++;  // on ajoute le maillon *t++ contenant g[k^1] en tête de la liste h[i] des successeurs de i
}
void graphe_dense_chaine(graphe_dense g, int nv, graphe_chaine h, liste p) //p est un tableau de maillon => maillon[NEMAX] p
{ int j, k;
  for(j=0; j<nv; j++) h[j] = 0;
  for(j=0; j<nv; j++)
  for(k=0; k<nv; k++)
   if(g[j][k]) //Si l'arc j->k existe,
    p->s = k, p->next = h[j], h[j] = p++; //on  ajoute k en tête de h[j]
}
void graphe_dense_succ(graphe_dense m, int nv, graphe_succ lim, int oriente)
{ int *succ=nv+1+lim, i, j, k=0;
  for(i=0; lim[i]=k,i<nv; i++)
  for(j=oriente?nv:i+1; j--; )
   if(m[i][j]) succ[k++]=j; //Si il y a un arc i->j on met son extrémité dans le tableau des successeurs
}
int graphe_dense_arcs(graphe_dense m, int nv, graphe_arcs g, int oriente) //return ne
{ int i, j, k=0;
  for(i=0; i<nv; i++)
  for(j=oriente?nv:i+1; j--; )  // On parcourt toute la matrice ou seulement la moitié sous la diagonale.
   if(m[i][j]) g[k++]=i, g[k++]=j;  // Si l'arc i->j existe on le range dans la liste des arcs.
  return k/2;
}
void graphe_arcs_succ(graphe_arcs g, int nv, int ne, graphe_succ lim, int oriente)
{ TETESUITE(oriente)
  for(int *succ=nv+1+lim, i=0, s=0; lim[s]=i,s<nv; s++)
  for(int k=tete[s]; k>=0; k=suite[k]) succ[i++]=g[k];  // On copie l'arc s->g[k]
}
void graphe_arcs_dense(graphe_arcs g, int nv, int ne, graphe_dense m, int oriente)
{ TETESUITE(oriente)
  for(int s=nv;s--;)
  { for(int t=nv;t--;) m[s][t]=0;
    for(int k=tete[s]; k>=0; k=suite[k]) m[s][g[k]]=1;  // On copie l'arc s->g[k]
  }
}
//***************************composantes connexes d'un graphe non orienté***************************
int nbcc_dense(graphe_dense g, int nv, int cc[])
{ int nb=0; //nb = nombre de composantes connexes déjà trouvées = numéro de la prochaine
  void dfs(int s)
  { cc[s]=nb;   // s est noté comme visité en lui attribuant le numéro de sa composante connexe
    for(int t=nv;t--;) if(g[s][t] && cc[t]<0) dfs(t); // tout voisin t de s non encore visité est visité
  }
  for(int s=nv;s--;)    cc[s]=-1;            // aucun sommet n'a encore été visité
  for(int s=nv;s--;) if(cc[s]<0) dfs(s),nb++;// tout sommet non encore visité, sera le point de départ pour l'exploration d'une nouvelle composante connnexe.
  return nb;                                 // nombre total de composantes connexes
}
int nbcc_arcs(graphe_arcs g, int nv, int ne, int cc[])
{ int nb=0;     // nombre de composantes connexes déjà trouvées = numéro de la prochaine
  TETESUITE(0)  // graphe non orienté
  void dfs(int s)
  { cc[s]=nb;   // s est noté comme visité en lui attribuant le numéro de sa composante connexe
    for(int k=tete[s];k>=0;k=suite[k]) if(cc[g[k]]<0) dfs(g[k]); // tout voisin g[k] de s non encore visité est visité
  }
  for(int s=nv;s--;)    cc[s]=-1;             // aucun sommet n'a encore été visité
  for(int s=nv;s--;) if(cc[s]<0) dfs(s),nb++; // tout sommet non encore visité, sera le point de départ pour l'exploration d'une nouvelle composante connnexe.
  return nb;                                  // nombre total de composantes connexes
}
/***************************composantes fortement connexes d'un graphe orienté***************************
L'algorithme de Tarjan cherche les composantes fortement connexes d'un graphes orienté.
On fait un parcours en profondeur d'abord.
Quand on atteint le premier sommet d'une composante fortement connexe, on ne le quittera qu'après avoir
visité tous les autres sommets de cette composante, (plus éventuellement d'autres composantes fortement connexes).
Si on est capable de reconnaître le premier sommet visité d'une nouvelle composante fortement connexe, on peut donc trouver les composantes fortement connexes:
Il suffit d'empiler chaque nouveau sommet visité et de dépiler à la fin de la visite du premier sommet s d'une composante, tous les sommets empilé depuis s.
Tarjan propose de numéroter les sommets dans l'ordre où on les atteint.
Pour chaque sommet s on calcule min(s) le plus bas numéro de sommet (n'appartenant pas à une autre composante) que l'on peut atteindre directement à partir d'un des descendants de
s dans l'arbre de parcours. Alors un sommet s est le premier d'une composante si min(s)=num(s).
On obtient l'algorithme suivant : */
#define MIN(a,b) ({ typeof(a) AAA=a, BBB=b; AAA<BBB?AAA:BBB; })
int nbcfc_arcs(graphe_arcs g, int nv, int ne, int num[])
{ int nbc=nv,   //les composantes fortement connexes recevront d'abord les numéros nv, nv+1, nv+2, ...
      pp[nv], *p=pp,  // pile des sommets déjà visités mais sans cfc attribuée.
      nbs=0;   // nombre de sommets déjà visités
  TETESUITE(1)
  int dfs(int s)
  { int min=num[*p++=s]=++nbs;          // min est initialisé avec le numéro num[s] du sommet s qui est empilé.
 // min sera le plus bas numéro de sommet (dans la même cfc) que l'on peut atteindre directement à partir d'un descendant du sommet s dans l'arbre de parcours.
    for(int k=tete[s];k>=0;k=suite[k])  // Chaque successeur g[k] de s non visité est visité
     min=MIN(min,num[g[k]]?:dfs(g[k])); //  et min est mis à jour en utilisant min(g[k]) pour un nouveau sommet ou num[g[k]] pour un ancien.
    if(min!=num[s]) return min;         // Si min n'a plus sa valeur initiale, il y a un chemin allant de s vers son père.
                                        // Sinon s est le premier élément d'une nouvelle composante fortement connexe,
    do num[*--p]=nbc; while(*p!=s);     // formée de tous les sommets empilés depuis s et non encore dépilés. On les dépile.
    return ++nbc;                       // On compte une composante fortement connexe de plus et on retourne un grand nombre (pour neutraliser le MIN)
  }
  for(int s=nv;s--;)     num[s]=0;      // Au début aucun sommet n'a été visité.
  for(int s=nv;s--;) if(!num[s]) dfs(s);// On commence le parcours en profondeur d'abord à partir de tout sommet non visité.
  for(int s=nv;s--;)     num[s]-=nv;    // Les composantes sont renumérotées 0, 1, 2, ...
  return nbc-nv;                        // nombre total de composantes fortement connexes.
}
//***********************parcours en largeur d'abord : plus court chemin (en nombre d'arcs)*************************
void dist_arcs(graphe_arcs g, int nv, int ne, int source, int dist[], int pere[])
{ TETESUITE(1)
  int s, t, k, file[nv], *p=file, *q=file;  // file d'attente
  for(s=nv;s--;) dist[s]=pere[s]=nv;    // Tous les sommets sont inaccessibles a priori.
  dist[*p++=pere[source]=source]=0;     // On met source en file d'attente.
  while(p>q)                            // Tant que la file d'attente n'est pas vide
   for(k=tete[s=*q++];k>=0;k=suite[k])  // on sort s de la file d'attente, et pour chacun de ses successeurs
    if(dist[t=g[k]]==nv)                //   t non encore atteint
     dist[*p++=t]=1+dist[pere[t]=s];    //    t sera atteint à partir de s en faisant un pas de plus
}
/*************************tas**************************************************************
Un tas est une structure de données qui permet de gérer un ensemble de nombres.
On peut :
-ajouter un nombre
-diminuer la valeur d'un nombre
-extraire le plus petit nombre
Ces opérations sont réalisées par les 3 procédures suivantes :
void tas_init(tas*h, int v[n], int n);
  Initialisation du tas.
  Les nombres gérés par le tas seront rangés dans le tableau v, et donc representés par des indices compris entre 0 et n-1.
  Le tas est vide.
void tas_set(tas*h, int i);
  est appelé quand le nombre v[i] doit être inséré dans le tas ou quand sa valeur a diminué alors qu'il était déjà dans le tas.
int tas_pop(tas*h);
  enlève le plus petit nombre du tas et rend son indice (dans le tableau v[])

Un tas peut être utilisé dans l'algorithme de Prim pour déterminer un arbre couvrant de poids minimal,
ou dans l'algorithme de Dijkstra pour déterminer les plus courts chemins à partir d'un sommet.
Dans les deux cas on appelle 1 fois tas_init(), ne fois tas_set() et nv fois tas_pop().
Pour un tas binaire le temps total est en O((ne+nv)ln(nv)).
Pour un tas de Fibonacci le temps total est en O(ne+nv ln(nv)).

Un tas binaire est un arbre binaire équilibré. Si le tas contient n nombres, les n noeuds du tas sont numérotés de 1 à n.
Le noeud numéro i à pour fils les noeuds de numéros 2i et 2i+1 (s'ils existent). Le noeud 1 est la racine.
Un nombre est toujours plus grand que son père. Les indices des nombres peuvent être rangés dans n cases conséscutive d'un tableau t.
Donc on a toujours v[t[i]]<=min(v[t[2*i]],v[t[2*i+1]]).
Lorsque l'on ajoute un élément dans le tas on range son indice dans t[++n].
Après avoir ajouté l'élément t[i], ou diminué sa valeur, on l'échange éventuellement avec son père s'il est plus petit que lui,
puis éventuellement avec son grand père, etc. Il remonte donc le long d'une branche jusqu'à ce qu'il ait in père plus petit que lui
ou qu'il atteigne le haut du tas.
De même quand on élimine le plus petit noeud du tas t[1], bouche le trou avec t[n--]. Il faut alors faire descendre cet élément dans le tas
le long d'une branche en l'échangeant éventuellement avec son plus petit fils s'il est plus petit que lui et en recommençant.
Il va donc descendre jusqu'à ce qu'il n'ait plus de fils ou que ses deux fils (ou son unique fils) soit plus grands que lui.
La longueur d'une branche étant inférieure à ln(n)/ln(2), chaque opération sur le tas prend un temps en O(ln(n)).
*/
#if 0
typedef struct { int n, *v; tnv t, u; } tas;  // tas binaire
#define t(i) h->t[(i)-1]    // t(i) est l'indice du nombre rangé dans le noeud i
#define v(i) h->v[t(i)]     // v(i) est le nombre rangé dans le noeud i
#define u(a) h->u[a]        // t(u(i))=i et u(t(i))=i  u(i)=0 si le nombre v(i) n'est pas dans le tas
#define n h->n              // nombre de nombres rangés dans le tas, taille du tas
void tas_init(tas*h, int v[], int m) { for(n=0,h->v=v;m;) u(--m)=0; }  // n=0 et u(0)=u(1)=u(2)=...=u(n)=0,le tas est vide
void tas_set(tas*h, int a)   // a est l'indice du nombre à (dé)placer dans le tas
{ int i=u(a), j, vi=h->v[a]; // i est le numéro du noeud et vi est sa valeur 
  if(!i) i=++n;              // On fait rentrer le nombre dans le tas s'il n'y était pas
  for(;(j=i/2) && v(j)>vi;i=j) u(t(i)=t(j))=i;  // tant que i a un père j plus grand que lui, on les échange, puis i/=2;
  u(t(i)=a)=i;               // On range a à sa place.
}
int tas_pop(tas*h)
{ if(!n) return -1;          // Le tas est vide 
  int r=t(1), i=1, a=t(n--), j, vi=h->v[a];  // r l'ancienne racine sera le résultat explicit de la fonction. On bouche le trou en 1 avec le noeud t(n--).
  u(r)=0;                    // r sort du tas   
  for(;j=2*i,j<=n && v(j+=j<n && v(j+1)<v(j))<vi;i=j) u(t(i)=t(j))=i;  // tant que i a un plus petit fils j(=2i ou 2i+1) plus petit que lui, on les échange.
  u(t(i)=a)=i;               // On range a à sa place
  return r;                  // Indice de l'ancien plus petit nombre du tas
}
#undef n
#undef u
#undef v
#undef t
#else
/* Un tas de Fibonacci est constitué d'une forêt. Chaque noeud a un degré qui est le nombre de ses fils.
Les fils d'un noeud quelconque ou les racines des arbres constituent une liste doublement chaînée, qui peut donc être représentée
par n'importe lequel de ses éléments. Cet ensemble est représenté par -1 quand il est vide.
2 arbres dont les racines sont de même degré d peuvent être fusionnés en un arbre dont la racine est de degré d+1,
en faisant de la racine de plus grosse clé le fils de l'autre. Un noeud dont la clef diminue doit être détaché de son père s'il devient
plus petit que lui. Un noeud qui n'est pas une racine est marqué quand il a perdu un fils.
Si il perd un deuxième fils on le détache de son père, qui devient marqué, ou se détache de son père s'il était déjà marqué.
On garde un pointeur sur le noeud ayant la plus petite clé. Quand on élimine le noeud ayant la plus petite clef, on ajoute la liste de ses fils
à la liste des racines des arbres, puis on recherche la plus petite clef parmi les racines des arbres.
Pour cela on fusionne d'abord les arbres de même degré en arbre de plus haut degré.
Un arbre de degre i a i fils de degrés supérieurs à i-2, i-3, i-4, ...,2, 1, 0, 0.
Donc le nombre de noeuds mimimal d'un arbre de degré i est f(i) avec
f(i+2)=f(i)+f(i-1)+f(i-2)+...+f(2)+f(1)+f(0)+f(0).
Donc f(i+2)=f(i+1)+f(i) avec f(0)=f(1)=1. Donc f(i) est la suite de Fibonacci. */
typedef struct { int *v, min; tnv av, ar, fils, pere, deg; } tas; // tas de Fibonacci
#define min h->min    // noeud ayant la plus petite clef. -1 si le tas est vide.
#define v(i) h->v[i]  // v(i) est la clef du noeud i
#define av(i) h->av[i]  // av et ar servent au chainage double : av(ar(i))=i=ar(av(i))
#define ar(i) h->ar[i]  // av(i) est le frère suivant ou la racine suivante.
#define deg(i) h->deg[i] // deg(i) est impair si le noeud est marqué car il a perdu un fils. Son degré est deg(i)/2. deg(i)=-1 si i n'est pas dans le tas.
#define fils(i) h->fils[i] // un des fils de i, -1 si i n'a pas de fils.
#define pere(i) h->pere[i] // pere de i, -1 si i est une racine.
void tas_aff(tas*h)
{ printf("min=%d  ",min); for(int i=0;i<20;i++) if(~deg(i)) printf("%d:%d<-%d->%dv%d^%d  ",deg(i),ar(i),i,av(i),fils(i),pere(i)); printf("\n"); }
void tas_init(tas*h, int v[], int m) { for(min=-1,h->v=v;m;) deg(--m)=-1; }   // Le tas est vide
int tas_lie(tas*h, int i, int j)  // union de 2 ensembles disjoints
{ if(i<0 || j<0) return i&j;      // Si l'un est vide on rend l'autre. (-1&a=a)
  int a=av(i), b=av(j);           // On échange les successeurs de i et de j.
  return ar(av(i)=b)=i, ar(av(j)=a)=j;
}
void tas_set(tas*h, int i)    // ajoute i au tas ou je détache de son père s'il est devenu plus petit que lui
{ int j, p, mi=min;
  if(0) printf("tas_set(%d):%d  ",i,v(i));
  if(deg(i)<0)            // si i n'était pas dans le tas, il forme un arbre à lui tout seul, que l'on ajoute
   deg(i)=0, fils(i)=pere(i)=-1, av(i)=ar(i)=i, tas_lie(h,i,mi);  // à la liste des racines.
  if(mi<0 || v(i)<v(mi)) min=i;  // si i est plus petit que l'ancien minimum, c'est lui le nouveau minimum
  if(p=pere(i),~p && v(i)<v(p))  // si i est devenu plus petit que son père p on le détache de son père
   do j=av(i), fils(p)= i!=j? av(ar(j)=ar(i))=j,ar(i)=av(i)=i,j :-1,  // i est enlevé de la liste des fils de p
    tas_lie(h,i,mi), pere(i)=-1, deg(i)&=~1,   // i est mis dans la liste des racines, il n'est plus marqué.
    p=pere(i=p), deg(i)-=2;          // le degré du père diminue d'un         
   while(~p && ~(deg(i)^=1)&1);      // s'il a un père il est marqué, ou détaché de son père (en itérant la boucle)
}
int tas_pop(tas*h)        // On élimine le plus petit élément, puis on cherche le nouveau plus petit
{ int mi=min, i, j, k, l, d;
  if(0) printf("tas_pop()=%d  ",mi),tas_aff(h);
  if(mi<0) return mi;     // Le tas est vide
  tas_lie(h,mi,fils(mi));  //On fusionne la liste des fils de min avec la liste des racines.
  deg(mi)=-1;                            // min est enlevé du tas
  static int t[40]={-2};                 // Par exemple t[6] contient une racine de degré 3 qui attend d'être appariée.
  if(*t==-2) for(i=40;i--;) t[i]=-1;     // Le tableau t est vide
  for(l=av(mi);l=av(j=l),j!=mi;t[deg(j)=d]=j)  // l fait le tour de la liste des racines, on traite la racine j de degré d
   for(d=deg(j)&~1;i=t[d],~i;    // si j peut être apparié avec i (de même degré), on met i dans la liste des fils de j, dont le degré augmente
        av(ar(i))=av(i), ar(av(i))=ar(i), av(i)=ar(i)=i, fils(pere(i)=j)=tas_lie(h,fils(j),i), t[d]=-1, deg(j)=d+=2)
    if(v(i)<v(j)) k=i, i=j, j=k;         // après avoir échangé éventuellement i et j.
  for(min=l;l!=mi;l=av(l)) if(pere(l)=t[deg(l)]=-1,v(l)<v(min)) min=l;  // On cherche le minimum parmi les racines non appariées.
  if(0) Affiche_tab(t,6), printf("min=%d mi=%d\n",min,mi);
  if(min==mi) min=-1; else j=av(mi), i=ar(mi), ar(j)=i, av(i)=j, ar(mi)=av(mi)=mi; // On enlève min de la liste des racines.
  if(0) printf("%10s",""), tas_aff(h);
  return mi;      // ancien minimum.
}
#undef min
#undef v
#undef av
#undef ar
#undef deg
#undef fils
#undef pere
#endif
/****************arbre couvrant de poids minimal : algorithme de Kruskal*****************************

F=la forêt formée des sommets du graphe G, mais sans aucune arête
Pour chaque arête s--t de G, prise dans l'ordre des poids croissants faire
  si s et t ne sont pas dans le même arbre de F alors
    on ajoute s--t à F

Cet algorithme construit la forêt F de poids minimal qui a les mêmes composantes connexes que G.
Si G est connexe alors F est un arbre.
Le temps de calcul est en O(ne ln(ne)) pour trier les arêtes de G par poids croissant,
et en O(ne ln(ln(nv)) si on utilise l'algorithme FIND-UNION pour gérer les composantes connexes de F lors de leur croissance.
Globalement, l'algorithme est en O(ne ln(nv)). L'algorithme de Prim avec des tas de Fibonacci est plus rapide.

*****************arbre couvrant de poids minimal : algorithme de Prim*****************************
A est un arbre qui va croître arête par arête.
Pour chaque sommet s hors de l'arbre, on définit pere[s] comme le sommet de A relié à s par une arête de poids minimal
et dist[s] comme le poids de cette arête. On a donc dist[s]=poids(s--pere[s]).
On part d'un arbre A réduit à un sommet isolé, et à chaque étape on cherche le sommet s hors de l'arbre qui minimise dist[s]
et on ajoute l'arête s--pere(s) à l'arbre A. Quand un sommet s entre dans l'arbre, les valeurs de pere(s) et dist(s)
se figent. Donc à la fin de l'algorithme, l'arbre A est constitué des arêtes s--pere[s].
En plus des 2 tableaux pere[nv] et dist[nv] on utilisera un tableau de booléens dehors[nv].
dehors[s] reste faux (nul) tant que le sommet s est hors de l'arbre et passe à vrai (1) quand il y rentre.
Le choix du premier sommet à intégrer l'arbre n'a pas d'importance, On peut donc prendre 0 par exemple.
Ce sommet sera son propre père.

Si le graphe est complet le poids des arêtes peut se ranger dans une matrice d[nv][nv] et
on peut initialiser pere[s]=0 pour tout s et se passer du tableau dist car dist[s]=poids(s--pere[s])=d[s][pere[s]].
*/
int prim_dense(graphe_dense d, int nv, int pere[])
{ int dehors[nv], s, t, c=0;              // c est la somme des poids des arêtes de l'arbre.
  for(s=nv;s--;) pere[s]=0, dehors[s]=1;  // tant que s n'est pas dans l'arbre, dehors[s]=1 et pere[s] est le sommet de l'arbre le plus proche de s.
  for(;;)
  { t=0;                                         // t restera nul jusqu'à ce qu'on trouve un sommet s hors de l'arbre
    for(s=nv;--s;) if(dehors[s])
      if(!t || d[s][pere[s]]<d[t][pere[t]]) t=s; // t est le sommet hors de l'arbre le plus proche de l'arbre
    if(!t) return c;                             // tous les sommets sont dans l'arbre
    dehors[t]=0, c+=d[t][pere[t]];               // On rattache t à l'arbre par l'arête t<->pere[t]
    for(s=nv;--s;) if(dehors[s])                 // et pour tout sommet s hors de l'arbre.
      if(d[s][t]<d[s][pere[s]]) pere[s]=t;       // et on met à jour pere[s].
  }
}
/* Toutes les boucles se font nv fois. Il y a deux niveaux de boucles, l'algorithme est en O(nv*nv).

Si le graphe est clairsemé, on peut le représenter par la liste de ses arêtes. On peut donner aussi la liste des poids des arêtes.
Par exemple l'arête g[4]--g[5] aura pour poids poids[5]. Et plus généralement poids(g[2i]--g[2i+1])=poids[2i+1] ou
poids(g[j]--g[j^1])=poids[j|1]. Seules les cases d'indice impair du tableau poids[2*nv] sont utilisées.
On ne peut plus se passer du tableau dist[].
On initalise pere[s]=-1 et dist[s]=infini (en fait -1u si dist[] est un tableau d'entiers non signés).
Les nombres dist[s] sont mis dans un tas, pour rechercher efficacement le plus petit d'entre eux.
Le temps de calcul est O((ne+nv)ln(nv)) si on utilise un tas binaire et O(ne+nv ln(nv)) si on utilise un tas de Fibonacci.
*/
int bavard=0;
int prim_arcs(graphe_arcs g, int nv, int ne, int poids[2*ne], int dist[], int pere[])
{ TETESUITE(0)   // graphe non orienté
  int dehors[nv], s, t, c=0, k;     // c est la somme des poids des arêtes de l'arbre.
  tas h; tas_init(&h,dist,nv);      // Le tas est vide.
  for(s=nv;s--;) dist[s]=pere[s]=-1, dehors[s]=1;  // Tous les sommets sont hors de l'arbre à une distance infinie.
  dist[0]=0, tas_set(&h,0);         // Au début le tas contient uniquement le sommet 0, qui va en sortir immédiatement pour entrer dans l'arbre.
  while(s=tas_pop(&h),s>=0)         // Tant que le tas n'est pas vide, on en retire le sommet le plus proche de l'arbre. Ce sommet s
   if(bavard && s? printf("p(%d->%d)=%d  ",s,pere[s],dist[s]),1 :1)
   for(c+=dist[s],dehors[s]=0,k=tete[s];k>=0;k=suite[k]) // est intégré à l'arbre puis pour chaque sommet t voisin de s,
    if(dehors[t=g[k]])              //  si t est hors de l'arbre            
     if(poids[k|1]+0u<dist[t]+0u)   //   et si l'arête s--t rapproche t de l'arbre  (On compare deux entiers non signés)
      dist[t]=poids[k|1], pere[t]=s, tas_set(&h,t);  // on en tient compte : dist[t] diminue et se déplace dans le tas.
  return c;                         // poids total de l'arbre construit
}
/*************************chemin de poids minimal : algorithme de Dijkstra************************************
Dans un graphe orienté, chaque arc a un poids positif. Le poids d'un chemin est la somme des poids de ses arcs.
On fixe un sommet dep. On définit dist[s] comme le poids minimal d'un chemin allant de dep à s.
On prend dist[s] infini s'il n'existe pas de chemin de dep vers s.
On a dist[dep]=0 et pour tout autre sommet s, dist[s]=min{dist[t]+poids(t->s)|t quelconque}.
Cette formule permet de calculer tous les dist[s] par récurrence en commençant par les petites valeurs.
*/
void dijkstra(graphe_arcs g, int nv, int ne, int poids[2*ne], int dep, int arr, int dist[], int pere[])
{ TETESUITE(1)   // graphe orienté
  tas h; tas_init(&h,dist,nv);           // Le tas est vide.
  for(int s=nv;s--;) dist[s]=pere[s]=-1; // Tous les sommets sont à une distance infinie.
  dist[dep]=0, tas_set(&h,dep);          // sauf le sommet dep qui à distance 0 (de lui mêe) que l'on met dans le tas
  int s, t;
  while(s=tas_pop(&h),s>=0 && s!=arr)    // Tant que le tas n'est pas vide, on en retire le sommet le plus proche. Ce sommet s    
   for(int k=tete[s];k>=0;k=suite[k])    // est définivement sorti du tas. dist[s] ne changera plus. Pour chaque sucesseur t de s
    if(dist[s]+poids[k]+0u<dist[t=g[k]]+0u) // s'il semble plus court d'aller en t en venant directement de s, alors
     pere[t]=s, dist[t]=dist[s]+poids[k], tas_set(&h,t); // on tient compte de ce plus court chemin en diminuant dist[t] et en le déplaçant dans le tas.
}
// On peut arrêter dès qu'on a calculé dist[arr], ou calculer tous les dist[s] en prenant par exemple arr=-1

/*********************flux maximal dans les réseaux de transport : algorithmes de Ford-Fulkerson, Edmonds-Karp et Dinic*********************
Un réseau (de transport) est un graphe orienté où chaque arc u->v possède une capacité (positive) c(u->v). On a de plus 2 sommets spéciaux,
la source et le puit.
Un flux (ou flot) dans ce réseau vérifie :
  Pour tout arc u->v  0<=f(u->v)<=c(u->v)
  Pour tout sommet s autre que la source ou le puit  la somme des f(s->t) est égale à la somme des f(t->s).
Autrement dit le flux entrant dans le sommet s est égal au flux sortant.

La valeur du flux est le flux sortant de la source (moins le flux entrant).
C'est aussi le flux entrant dans le puit (moins le flux sortant).
Etant donné un réseau, on cherche un flux de valeur maximale.

Pour un flux f, on définit la capacité résiduelle par c(f)(u->v)=c(u->v)-f(u->v) et c(f)(v->u)=f(u->v).
C'est donc un graphe ayant deux fois plus d'arcs que le réseau initial.
Pour que cette notation ait un sens on suppose donc que dans le réseau initial l'arc v->u n'existe pas si l'arc u->v existe.
Mais cette condition n'est pas vraiment indispensable : On pourrait considérer qu'il y a deux arcs u->v dans le nouveau graphe,
mais on pourrait aussi les fusionner en un seul en additionnant leurs capacités : c(f)(u->v)=c(u->v)-f(u->v)+f(v->u).

Le graphe résiduel est le graphe formé des arcs dont la capacité résiduelle est strictement positive.
Un chemin augmentant est un chemin de la source au puit dans le graphe résiduel.

Un chemin augmentant permet d'augmenter la valeur du flux d'une quantité égale à la plus petite
capacité résiduelle dans les arcs constituant le chemin.

On peut partir d'un flux nul, puis chercher un chemin augmentant et l'utiliser pour augmenter le flux,
puis en chercher un autre et recommencer indéfiniment, jusqu'à ce qu'il n'y ait plus de chemin augmentant.
On peut démontrer qu'on obtient ainsi un flux maximal.
C'est l'algorithme de Ford et Fulkerson.

Cet algorithme peut être très lent. Par exemple avec le réseau
c(S->A)=c(A->P)=c(S->B)=c(B->P)=1000 et c(A->B)=1 si la source est S et le puit P,
on peut faire 2000 itérations en prenant 1000 fois les chemins augmentant  S->A->B->P  puis S->B->A->P.
Dans certains cas, quand les capacités ne sont pas rationnelles, on peut boucler indéfiniment sans même converger vers la valeur optimale.
Par exemple avec c(S->A)=c(S->C)=c(S->D)=c(B-C)=c(A->P)=c(B->P)=c(D->P)=c(S->P)=100, c(A->B)=(1+sqrt(5))/2, c(C->D)=1,
on peut répéter indéfiniment la suite de 4 chemins augmentants S->A->B->C->D->P, S->D->C->B->P, S->A->B->C->D->P et S->C->B->A->P.
Edmonds et Karp ont amélioré cet algorithme en imposant que le chemin augmentant soit de longueur minimale (en nombre d'arcs).
La recherche du chemin augmentant doit donc se faire par un pacours en largeur d'abord du graphe résiduel.
Alors la longueur l du chemin augmentant ne diminue pas d'une itération à l'autre.
De plus tant que le plus court chemin garde la même longueur l,
l'ensemble des arcs appartenant à un chemin de longueur l de la source vers le puit diminue strictement d'une itération à la suivante.
Il y a donc moins de ne itérations consécutives avec la même valeur de l.
Il y a moins de nv valeurs possible pour l (car l<nv).
Chaque itération est un parcours de graphe et se fait donc en O(ne).
Donc l'algorithme d'Edmonds et Karp s'arrête toujours au bout d'un temps en O(ne*ne*nv).
La méthode de Dinic améliore cet algorithme en regroupant toutes les itérations correspondant à la même valeur de l.
Pour une valeur de l, on fait d'abord un seul parcours en largeur d'abord qui détermine la distance dist(u) de chaque sommet u
à la source dans le graphe résiduel. Après cela on émonde le graphe résiduel en ne gardant que les arcs de la forme
u->v avec dist(v)=dist(u)+1. Puis on fait un seul parcours en profondeur d'abord dans ce graphe pour trouver tous les chemins augmentant
de longueur l.
Le nombre de valeurs de l est toujours majoré par nv.
Le nombre de chemins augmentant trouvés pendant le parcours en profondeur d'abord est toujours majoré par ne.
Le traitement de chaque chemin augmentant trouvé est maintenant en O(l)=O(nv).
Le temps de calcul global est en O(nv*nv*ne).
Dans le temps de calcul on a remplacé un facteur ne par un facteur nv, car maintenant pour chaque chemin augmentant trouvé,
on ne parcourt que le chemin et non plus tout le graphe.
En fait on peut encore améliorer cet algorithme en utilisant des arbres dynamiques, et ramener le temps de traitement de chaque
chemin augmentant à O(ln nv), ce qui donne un temps de calcul global en O(nv*ne*ln nv).
L'algorithme de Dinic est (2 fois) plus compliqué à programmer que l'algorithme d'Edmonds et Karp,
car la boucle contient un parcours en largeur d'abord suivi d'un parcours en profondeur d'abord,
au lieu d'un seul parcours en largeur d'abord.

Au lieu de mettre à jour le flux puis de calculer la capacité résiduelle à partir de la capacité et du flux, il est plus simple
de ne garder que la capacité résiduelle : On remplace f(u->v)+=c par c(f)(u->v)-=c, c(f)(v->u)+=c.
En fait dans la procédure dinic() qui suit, la capacité résiduelle est rangée dans le tableau flux[].
En entrée si par exemple la capacité de l'arc g[4]->g[5] est 23 on doit avoir flux[4]=0 et flux[5]=23.
A la fin de la procédure, si par exmple le flux dans cet arc est 7, on aura flux[4]=7 et flux[5]=16.
Plus généralement la capacité résiduelle de l'arc g[i]->g[i^1] est flux[i^1].

Le graphe résiduel et le graphe résiduel émondés sont virtuels : Au lieu de fabriquer explicitement la liste de leurs
arcs, on garde la liste des arcs du graphe initial, et en la parcourant on ignore les arcs de capacité nulle, ou qui n'éloignent pas de la source.

La procédure tetesuite() est appelée à chaque itération de la boucle externe et refait exactement les mêmes calculs. Le tableau suite[] est donc recalculé
alors que sa valeur n'a pas changé. Seul le tableau tete[] a besoin d'être recalculé, car lors du parcours en profondeur d'abord, les listes de successeurs
sont vidées au fur et à mesure que les arcs sont éliminés du graphe résiduel émondé.

La procédure récursive dfs() qui fait le parcours en profondeur d'abord, gère les chemins augmentants et l'augmentation du flux qu'ils produisent.
Deux chemins augmentants différents peuvent avoir un début commun et une fin commune. La fin commune est traitée en faisant deux fois la même suite
d'appels récursifs. Par contre le début commun correspond à une seule suite d'appels récursifs avec un flux qui est la somme des flux.
*/
int dinic(graphe_arcs g, int nv, int ne, int flux[2*ne], int source, int puit)
{ int f=0;
  for(;;)
  { TETESUITE(0)
    int s, t, k, file[nv], *p=file, *q=file, dist[nv];
    for(s=nv;s--;) dist[s]=nv;            // parcourt en largeur d'abord pour déterminer la distance à la source dans le graphe formé des arcs dont le flux peut augmenter.
    dist[*p++=source]=0;                  // On met source en file d'attente.
    while(p>q && (s=*q++)!=puit)          // Tant que la file d'attente n'est pas vide
     for(k=tete[s];k>=0;k=suite[k])       // on sort s de la file d'attente, et chacun des arcs non saturés sortant de s et allant vers un sommet
      if(flux[k] && dist[t=g[k]]==nv)     //   t non encore atteint nous apprend que
       dist[*p++=t]=1+dist[s];            //    t sera atteint à partir de s en faisant un pas de plus
    if(s!=puit) return f;                 // Le flux est maximal quand le puit ne peut plus être atteint.
    unsigned dfs(int s, unsigned fmax)    // Parcours en profondeur d'abord du graphe formé des arcs qui augmentent la distance à la source.
                                          // fmax est le flux maximal possible dans le chemin courant de la source à s.
    { if(s==puit) return fmax;            // On a atteint le puit, on peut donc faire passer le flux maximal.
      int k=tete[s]; unsigned f=0, df;    // 0<=f<=fmax  f est le flux que l'on a déjà réussi à faire passer.
      for(;k>=0;k=suite[k])               // Chaque arc s->g[k] de capacité flux[k]
       if(flux[k] && dist[t=g[k]]==dist[s]+1)  // non saturé et menant à un sommet plus éloigné
        if(f+=df=dfs(t,MIN(fmax-f,flux[k])),   // va peut-être permettre de faire passer un flux min(...,...)
         flux[k]-=df, flux[k^1]+=df, f==fmax) break; // le flux df passant dans cet arc est pris en compte. Si f==fmax cet arc n'a peut-être pas été utilisé à fond, on le garde.
      return tete[s]=k, f;
    }
    f+=dfs(source,-1u);                   // -1u est le plus grand entier non signé.
  }
}
void set0(graphe_arcs g, int ne) { for(;ne--;) g[2*ne]=0; }
void set1pere(graphe_arcs g, int ne, graphe_arcs poids, int pere[])
{ for(int k=2*ne;k--;) if(pere[g[k]]==g[k^1]) poids[k&~1]++;
}
void dessin_arbre(graphe_arcs g,int nv, int ne, int poids[], int pere[], int dist[])
{ if(poids && pere) set1pere(g,ne,poids,pere);
  if(graphe_aff) graphe_aff(poids?:g,dist); else
  { if(poids) Affiche_tab(poids,2*ne);
    if(pere ) Affiche_tab(pere ,nv);
    if(dist ) Affiche_tab(dist ,nv);
  }
  if(poids && pere) set0(poids,ne);
}
void test1234(int nv, int ne, graphe_dense g1, graphe_chaine g2, graphe_succ g3, graphe_arcs g4, int s, int oriente)
{ int poids[2*ne], nv0=nv<30?nv:0, mp[nv0][NVMAX], pere[nv], dist[nv], *cc=dist;
  printf("test1234 nv=%d ne=%d oriente=%d\n",nv,ne,oriente);
  printf("nombre de sommets atteints a partir de %d :",s);
  if(g1) printf(" %d",nbatteint1(g1,nv,s));
  printf(" %d %d %d\n",nbatteint2(g2,nv,s),nbatteint3(g3,nv,s),nbatteint4(g4,nv,ne,oriente,s));
  if(g1) printf("nbcc=%d  ",nbcc_dense (g1,nv,cc)), affiche_tab(cc,nv);
  printf("nbcc=%2d  ",(oriente?nbcfc_arcs:nbcc_arcs)(g4,nv,ne,cc)), dessin_arbre(g4,nv,ne,0,0,cc); 
  poids_arcs_aleat(poids,ne,5);
  for(int i=nv0;i--;) for(int j=nv;j--;) mp[i][j]=30000;
  if(nv0) for(int k=0;k<2*ne;k+=1+oriente) mp[g4[k]][g4[k^1]]=poids[k|1];
  if(oriente)
  printf("dijkstra\n"), dijkstra(g4,nv,ne,poids,0,-1,dist,pere), dessin_arbre(g4,nv,ne,poids,pere,dist),
  printf("dinic\n"),    dinic   (g4,nv,ne,poids,0,nv-1),         dessin_arbre(g4,nv,ne,poids,0   ,0   );
  else
  { if(nv0) printf("prim()=%d\n",prim_dense(mp,nv,      pere)), dessin_arbre(g4,nv,ne,poids,pere,0   );
    printf("prim()=%d\n",prim_arcs (g4,nv,ne,poids,dist,pere)), dessin_arbre(g4,nv,ne,poids,pere,dist);
  }
}
void test1(int nv, int ne, graphe_dense g1, int s)
{ int g4[2*ne], g3[nv+ne+1];
  if(ne!=graphe_dense_arcs(g1,nv,g4,1)) printf("test1 rate ne faux\n");
  maillon *g2[nv], p[ne];
  graphe_dense_chaine(g1,nv,g2,p);
  graphe_dense_succ  (g1,nv,g3,1);
  test1234(nv,ne,g1,g2,g3,g4,s,1);
}
void test4(int nv, int ne, graphe_arcs g4, int s)
{ int g3[nv+2*ne+1];
  maillon *g2[nv], p[2*ne];
  for(int ori=2;ori--;)
  { graphe_arcs_chaine(g4,nv,ne,g2,ori,p);
    graphe_arcs_succ  (g4,nv,ne,g3,ori);
    test1234(nv,ne,0,g2,g3,g4,s,ori);
  }
}
void dessin_arbre_tore(graphe_arcs g, int nv, int ne, int h, int*poids, int*dist)
{ int pos[nv];
  TETESUITE(0)
  int dp(int k)
  { int d=g[k]-g[k^1]; if(d<-h) d+=nv; if(d>h) d-=nv; return d>1?256:d<-1?-256:d; }
  void dfs(int s, int p)
  { if(pos[s]) return;
    pos[s]=p;
    for(int k=tete[s];~k;k=suite[k]) if(poids[k|1]>0) dfs(g[k],p+dp(k));
  }
  for(int s=nv;s--;) pos[s]=0;
  int min(int a, int b) { return a<b?a:b; }
  int max(int a, int b) { return a<b?b:a; }
  int m=128, M=m, mm=m, MM=m, p, s, d;
  dfs(0,m);
  for(s=nv;s--;) mm=min(mm,p=pos[s]), MM=max(MM,p), m=min(m,p&=255), M=max(M,p);
  m+=(mm|255)-512, M+=(MM|255)+2-m;
  int t[2*M];
  for(s=2*M;s--;) t[s]=0;
  for(s=nv;s--;) p=pos[s]-m, t[pos[s]=2*p]=s+(dist?dist[s]<<8:0); t[*pos]=-1;
  for(int k=2*ne;k--;k--) d=dp(k), t[pos[g[k]]-d]=t[pos[g[k-1]]+d]=poids[k];
  for(s=256;printf("\n"),s<2*M;s=(s|255)+1) for(;(++s&255)<(2*M&255);) if(p=t[s],p>255) printf("%2d:%-3d",p&255,p>>8); else if(p) printf("%4d  ",p); else printf("%6s","");
}
void dessin_arbre_tore_dijkstra(graphe_arcs g, int nv, int ne, int h, int*poids, int*pere, int*dist)
{ int poi[2*ne], s, t, k, S;
  for(k=2*ne;k--;poi[--k]=0) s=g[k-1], t=g[k], S=pere[t], poi[k]=S==s? poids[k] :t&&dist[s]<=dist[S]? -poids[k] :0;  dessin_arbre_tore(g,nv,ne,h,poi,dist);
}
void dessin_arbre_tore_prim(graphe_arcs g, int nv, int ne, int h, int*poids, int*pere)
{ int poi[2*ne], s, t, k;
  for(k=2*ne;k--;poi[--k]=0) s=g[k-1], t=g[k], poi[k]=s==pere[t]||t==pere[s]? poids[k] :0;  
  dessin_arbre_tore(g,nv,ne,h,poi,0);
}
void examtore17(int z)
{ graphe_arcs g;
  int nv=17, h=4, ne=tore(nv,h,g), poids[2*ne], pere[nv], dist[nv], k;
  poids_arcs_aleat(poids,ne,z);
  printf("sujet %d\n",z);
  for(k=0;k<ne;k++) printf("p(%d->%d)=%d  ",g[2*k],g[2*k+1],poids[2*k+1]); printf("\n");
  if(0) return;
  printf("prim()=%d\n",prim_arcs (g,nv,ne,poids,dist,pere)), /*dessin_arbre(g,nv,ne,poids,pere,dist),*/ dessin_arbre_tore_prim(g,nv,ne,h,poids,pere);
  printf("dijkstra\n"), dijkstra(g,nv,ne,poids,0,-1,dist,pere), /*dessin_arbre(g,nv,ne,poids,pere,dist),*/ dessin_arbre_tore_dijkstra(g,nv,ne,h,poids,pere,dist);
}
void exam()
{ bavard=1; for(int z=0;z++<24;) examtore17(z);
}
int main(int argc, char**argv)
{ if(0) test1234(5,8,g1,g2,g3,g4,2,1);
  if(0) test1234(5,7,h1,h2,h3,h4,2,0);
  int nv=10, ne=30, m[nv][NVMAX];
  graphe_dense_aleat(nv,ne,m,4);
  if(0) for(int i=0;i<nv;i++) affiche_tab(m[i],nv);
  if(0) test1(nv,ne,m,nv/2);
  graphe_arcs g;
  if(0) ne=tore     (nv=29, 6, g), flip_arcs(g,ne,1), graphe_aff(g,0), test4(nv,ne,g,nv/2);
  if(0) hypercube(4, &nv, &ne, g), flip_arcs(g,ne,1),                  test4(nv,ne,g,nv/2);
  if(0) grille(7, 5, &nv, &ne, g), flip_arcs(g,ne,1), graphe_aff(g,0), test4(nv,ne,g,nv/2);
  if(1) exam();
  return 0;
}