// Este arquivo: GRAPHlists.c
// Data: 2019-12-31
// Autor: Paulo Feofiloff
//
// Este é o rascunho da implementação de uma biblioteca de manipulação de grafos
// representados por listas de adjacência. Veja detalhes no arquivo-interface
// GRAPHlists.h.
//
// Tudo foi extraído de www.ime.usp.br/~pf/algoritmos_para_grafos/, que copiou
// muita coisa do livro "Algorithms", 3rd.ed., part 5, de Sedgewick.
////////////////////////////////////////////////////////////////////////////////


#define DEBUG true


// Estruturas de dados básicas
////////////////////////////////////////////////////////////////////////////////

#include "GRAPHlists.h"
// A interface GRAPHlists.h define a estrutura graph e o tipo-de-dados Graph. 
// Também contém as interfaces STACK.h, QUEUE.h, PQ.h, maxPQ.h, UF.h e
// MYTOOLS.h. Também contém as interfaces padrão stdlib.h, stdio.h, string.h,
// limits.h e stdbool.h.



// Ferramentas para construção de grafos
////////////////////////////////////////////////////////////////////////////////

Graph 
GRAPHinit( int V) { 
   Graph G = mallocc( sizeof *G);
   G->V = V; 
   G->A = 0;
   G->adj = mallocc( V * sizeof (link));
   for (vertex v = 0; v < V; ++v) 
      G->adj[v] = NULL;
   return G;
}

// Função privada (= static) auxiliar usada para construir listas de adjacência.
// A função recebe um vértice w e o endereço next de um nó e devolve o endereço
// a de um novo nó tal que a->w == w e a->next == next. 
static link 
NEWnode( vertex w, link next) { 
   link a = mallocc( sizeof (struct node));
   a->w = w; 
   a->next = next;     
   return a;                         
}

// Função privada auxiliar usada para construir listas de adjacência. Esta é uma
// versão de NEWnode() apropriada para grafos com custos (ou capacidades) nos
// arcos.
static link 
NEWnode_c( vertex w, link next, int c) { 
   link a = mallocc( sizeof (struct node));
   a->w = w; 
   a->next = next;     
   a->c = c;     
   return a;                         
}

void 
GRAPHinsertArc( Graph G, vertex v, vertex w) { 
   for (link a = G->adj[v]; a != NULL; a = a->next) 
      if (a->w == w) return;
   G->adj[v] = NEWnode( w, G->adj[v]);
   G->A++;
}

void 
GRAPHinsertArc_c( Graph G, vertex v, vertex w, int c) { 
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      if (a->w == w) {
         a->c = c; // atualiza custo de arco existente
         return;
      }
   }
   G->adj[v] = NEWnode_c( w, G->adj[v], c);
   G->A++;
}

void 
UGRAPHinsertEdge( UGraph G, vertex v, vertex w) { 
   GRAPHinsertArc( G, v, w);
   GRAPHinsertArc( G, w, v);
}

void 
UGRAPHinsertEdge_c( UGraph G, vertex v, vertex w, int c) { 
   GRAPHinsertArc_c( G, v, w, c);
   GRAPHinsertArc_c( G, w, v, c);
}

void 
GRAPHremoveArc( Graph G, vertex v, vertex w) {
   link *aa = &(G->adj[v]); // A
   while (*aa != NULL && (*aa)->w != w)
      aa = &(*aa)->next; // B
   if (*aa != NULL) {
      link b = *aa;
      *aa = b->next;
      free( b);
      G->A--;
   }
}
// Observação A: &G->adj[v] significa &(G->adj[v])
// Observação B: &(*aa)->next significa &((*aa)->next) e
//               é diferente de *aa->next

void 
UGRAPHremoveEdge( UGraph G, vertex v, vertex w) {
   GRAPHremoveArc( G, v, w);
   GRAPHremoveArc( G, w, v);
}

void 
GRAPHshow( Graph G) { 
   for (vertex v = 0; v < G->V; ++v) {
      printf( "%2d:", v);
      for (link a = G->adj[v]; a != NULL; a = a->next)
         printf( " %2d", a->w);
      printf( "\n");
   }
}

void 
GRAPHshow_c( Graph G) { 
   for (vertex v = 0; v < G->V; ++v) {
      printf( "%2d:", v);
      for (link a = G->adj[v]; a != NULL; a = a->next)
         printf( " %2d (%2d)", a->w, a->c);
      printf( "\n");
   }
}

void 
GRAPHshowArcs( Graph G) { 
   for (vertex v = 0; v < G->V; ++v)
      for (link a = G->adj[v]; a != NULL; a = a->next)
         printf( "%d %d\n", v, a->w);
}

void 
GRAPHshowArcs_c( Graph G) { 
   for (vertex v = 0; v < G->V; ++v)
      for (link a = G->adj[v]; a != NULL; a = a->next)
      printf( "%2d %2d %2d\n", v, a->w, a->c);
}

Graph 
GRAPHcopy( Graph G) {
   Graph H = GRAPHinit( G->V);
   for (vertex v = 0; v < G->V; ++v) 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         GRAPHinsertArc( H, v, a->w); 
   return H;   
}

// Função privada auxiliar usada por GRAPHdestroy(). Libera os nós da lista
// encadeada lst.
static void 
freelist( link lst) {
   if (lst != NULL) {
      freelist( lst->next);
      free( lst);
   }
}

// Esta é uma função-invólucro (= wrapper function). O serviço pesado é
// executado por freelist().
void 
GRAPHdestroy( Graph G) {
   for (vertex v = 0; v < G->V; ++v)
      freelist( G->adj[v]);
   free( G->adj);
   free( G);   
}

int
GRAPHoutdeg( Graph G, vertex v) {
   int outdeg = 0;
   for (link a = G->adj[v]; a != NULL; a = a->next) 
      outdeg++;
   return outdeg;
}

Graph 
GRAPHreverse( Graph G) {
   Graph GR = GRAPHinit( G->V);
   for (vertex v = 0; v < G->V; ++v)
      for (link a = G->adj[v]; a != NULL; a = a->next) 
         GRAPHinsertArc( GR, a->w, v);
   return GR;
}

// Função privada auxiliar usada por invertLists(). A função inverte a lista de
// adjacência que começa em a e devolve o endereço do primeiro nó da nova lista.
static link 
invertR( link a) {
   if (a == NULL) return NULL;
   if (a->next == NULL) return a; // base da recursão
   link b = a->next;
   link aa = invertR( b);
   b->next = a;
   a->next = NULL;
   return aa;
}

// Esta função inverte as listas de adjacência de todos os vértices do grafo G. 
// Por exemplo, se os 4 vizinhos de um certo vértice u aparecem na ordem v w x y
// na lista G->adj[u], então depois da aplicação da função os vizinhos aparecem
// na ordem y x w v. Esta é uma função-invólucro (= wrapper function). O
// serviço pesado é executado por invertR().
static void 
invertLists( Graph G) {
   for (vertex v = 0; v < G->V; ++v) 
      G->adj[v] = invertR( G->adj[v]);
}

// Esta é uma versão não recursiva de invertLists().
static void 
invertLists_i( Graph G) {
   for (vertex v = 0; v < G->V; ++v) {
      link a = NULL; // anterior
      link b = G->adj[v]; // corrente
      while (b != NULL) {
         link c = b->next; // seguinte
         b->next = a;
         a = b;
         b = c;
      }
      G->adj[v] = a;
   }
}

Graph 
GRAPHinputArcs( FILE *infile) {
   int V, A;
   fscanf( infile, "%d %d", &V, &A);
   Graph G = GRAPHinit( V);
   for (int i = 0; i < A; ++i) {
      vertex v, w;
      fscanf( infile, "%d-%d", &v, &w);
      GRAPHinsertArc( G, v, w);
   }
   invertLists_i( G);
   return G;
}

// Usa fgets() and strtok().
Graph 
GRAPHinputAdjLists( FILE *infile) {
   char line[LINE_MAX];
   fgets( line, LINE_MAX, infile); // A
   string token = strtok( line, " \n"); // delimitadores: ' ' e '\n'
   // token != NULL
   int V = strtol( token, NULL, 10);
   Graph G = GRAPHinit( V);
   for (int i = 0; i < V; i++) {
      fgets( line, LINE_MAX, infile); // A
      token = strtok( line, " :\n");  // delimitadores: ' ', ':' e '\n'
      // token != NULL
      vertex v = strtol( token, NULL, 10); // 0 <= v < V
      while ((token = strtok( NULL, " \n")) != NULL) {
         vertex w = strtol( token, NULL, 10); // 0 <= w < V
         GRAPHinsertArc( G, v, w);
      } // terminou processamento dos vizinhos de v
   }
   invertLists_i( G);
   return G;
}
// A: line[] contém uma linha de infile;
//    se n = strlen( line) então line[n] == '\0', n > 0 e line[n-1] != '\n'.

// Usa fgets() and strtok().
Graph 
GRAPHinputAdjLists_c( FILE *infile) {
   char line[LINE_MAX];
   fgets( line, LINE_MAX, infile); // A
   string token = strtok( line, " \n"); // token != NULL
   int V = strtol( token, NULL, 10);
   Graph G = GRAPHinit( V);
   for (int i = 0; i < V; i++) {
      fgets( line, LINE_MAX, infile); // A
      token = strtok( line, " :\n"); // token != NULL
      vertex v = strtol( token, NULL, 10); // 0 <= v < V
      while ((token = strtok( NULL, " \n")) != NULL) {
         vertex w = strtol( token, NULL, 10); // 0 <= w < V
         token = strtok( NULL, " \n");
         int c = strtol( token, NULL, 10);
         GRAPHinsertArc_c( G, v, w, c);
      } // terminou processamento dos vizinhos de v
   }
   invertLists_i( G);
   return G;
}
// A: line[] contém uma linha de infile;
//    se n = strlen( line) então
//    n < LINE_MAX, line[n] == '\0', n > 0 e line[n-1] != '\n'.

void
UGRAPHedges( UGraph G, edge e[]) {
   int i = 0;
   for (vertex v = 0; v < G->V; ++v) 
      for (link a = G->adj[v]; a != NULL; a = a->next) 
         if (v < a->w) {
            e[i].v = v;
            e[i].w = a->w;
            e[i].c = a->c;
            ++i;
         }
}



// Numerações e permutações de vértices
////////////////////////////////////////////////////////////////////////////////

void
perm2num( int V, vertex perm[], int num[]) { 
   for (int i = 0; i < V; ++i) 
      num[perm[i]] = i; 
}



// Grafos topológicos
////////////////////////////////////////////////////////////////////////////////

// Eliminação iterada de fontes.
bool 
GRAPHtopol( Graph G, int topo[]) { 
   int *indeg = mallocc( G->V * sizeof (int));
   for (vertex v = 0; v < G->V; ++v) indeg[v] = 0;
   for (vertex v = 0; v < G->V; ++v) 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         indeg[a->w] += 1;
   vertex *fila = mallocc( G->V * sizeof (vertex));
   int comeco = 0, fim = 0;
   for (vertex v = 0; v < G->V; ++v)
      if (indeg[v] == 0) 
         fila[fim++] = v;
   int k = 0;
   while (comeco < fim) { 
      // fila[comeco..fim-1] de fontes virtuais
      vertex v = fila[comeco++];
      topo[v] = k++;
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         indeg[a->w] -= 1; // remoção virtual do arco v-w
         if (indeg[a->w] == 0) 
            fila[fim++] = a->w;
      }
   }
   free( indeg); free( fila);
   return k >= G->V;
}



// Grafos aleatórios
////////////////////////////////////////////////////////////////////////////////

vertex 
randV( Graph G) { 
   double r = rand() / (RAND_MAX + 1.0); // 0 <= r < 1
   return r * G->V;
}

// Supõe que A <= V*(V-1). Código inspirado no Programa 17.7 de Sedgewick.
Graph 
GRAPHrand( int V, int A) { 
   Graph G = GRAPHinit( V);
   while (G->A < A) {
      vertex v = randV( G);
      vertex w = randV( G);
      if (v != w) 
         GRAPHinsertArc( G, v, w);
   }
   return G;
}

// Supõe que E <= V*(V-1)/2. Código inspirado no Programa 17.7 de Sedgewick.
UGraph 
UGRAPHrand( int V, int E) { 
   UGraph G = UGRAPHinit( V);
   int A = 2*E;
   while (G->A < A) {
      vertex v = randV( G);
      vertex w = randV( G);
      if (v != w)
         UGRAPHinsertEdge( G, v, w);
   }
   return G;
}

// Código inspirado no Programa 17.7 de Sedgewick.
Graph 
GRAPHrand_c( int V, int A, int cmin, int cmax) { 
   Graph G = GRAPHinit( V);
   while (G->A < A) {
      vertex v = randV( G);
      vertex w = randV( G);
      int c = randInteger( cmin, cmax);
      if (v != w) 
         GRAPHinsertArc_c( G, v, w, c);
   }
   return G;
}

UGraph 
UGRAPHrand_c( int V, int E, int cmin, int cmax) { 
   UGraph G = UGRAPHinit( V);
   int A = 2*E;
   while (G->A < A) {
      vertex v = randV( G);
      vertex w = randV( G);
      int c = randInteger( cmin, cmax);
      if (v != w) 
         UGRAPHinsertEdge_c( G, v, w, c);
   }
   return G;
}

// Erdős-Rényi.
Graph 
GRAPHrandER( int V, int A) { 
   double prob = (double) A / (V*(V-1));
   Graph G = GRAPHinit( V);
   for (vertex v = 0; v < V; ++v)
      for (vertex w = 0; w < V; ++w) 
         if (v != w)
            if (rand( ) < prob*(RAND_MAX+1.0))
               GRAPHinsertArc( G, v, w);
   return G;
}

UGraph 
UGRAPHrandER( int V, int E) { 
   double prob = (double) 2*E / (V*(V-1));
   UGraph G = GRAPHinit( V);
   for (vertex v = 0; v < V; ++v)
      for (vertex w = 0; w < V; ++w) 
         if (v != w)
            if (rand( ) < prob*(RAND_MAX+1.0))
               UGRAPHinsertEdge( G, v, w);
   return G;
}

Graph 
GRAPHrandER_c( int V, int A, int cmin, int cmax) { 
   double prob = (double) A / (V*(V-1));
   Graph G = GRAPHinit( V);
   for (vertex v = 0; v < V; ++v)
      for (vertex w = 0; w < V; ++w)
         if (v != w && rand( ) < prob*(RAND_MAX+1.0))
            GRAPHinsertArc_c( G, v, w, randInteger( cmin, cmax));
   return G;
}



// Construtores de grafos
////////////////////////////////////////////////////////////////////////////////

Graph 
GRAPHbuildComplete( int V) {
   Graph G = GRAPHinit( V);
   for (vertex v = 0; v < G->V; ++v)
      for (vertex w = 0; w < G->V; ++w)
         if (w != v)
            GRAPHinsertArc( G, v, w);
   return G;
}

Graph 
GRAPHrandPath( int V) {
   Graph G = GRAPHinit( V);
   vertex *vv = mallocc( V * sizeof (vertex));
   for (int i = 0; i < V; ++i) vv[i] = i;
   randPermutation( vv, V);
   for (int i = 0; i < V-1; ++i)
      GRAPHinsertArc( G, vv[i], vv[i+1]);
   free( vv);
   return G;
}

// Supõe que m >= 1, n >= 1 e E <= m*n.
UGraph 
UGRAPHrandBipartite( int m, int n, int E) {
   UGraph G = UGRAPHinit( m+n);
   vertex *vv = mallocc( (m+n) * sizeof (vertex));
   for (int i = 0; i < m+n; ++i) vv[i] = i;
   randPermutation( vv, m+n);
   while (G->A < 2*E) {
      double r = rand( ) / (RAND_MAX + 1.0);
      int i = r*m;
      r = rand( ) / (RAND_MAX + 1.0);
      int j = m + r*n;
      UGRAPHinsertEdge( G, vv[i], vv[j]);
   }
   free( vv);
   return G;
}



// Caminhos e ciclos em grafos
////////////////////////////////////////////////////////////////////////////////



// Acessibilidade (caminho de um vértice a outro)
////////////////////////////////////////////////////////////////////////////////

// Função privada auxiliar usada por GRAPHreach(). A função visita todos os
// vértices de G que podem ser alcançados a partir de v sem passar por vértices
// já visitados. 
static void 
reachR( Graph G, vertex v, bool *visited) { 
   visited[v] = true;
   for (link a = G->adj[v]; a != NULL; a = a->next)
      if (!visited[a->w])
         reachR( G, a->w, visited);
}

// Esta é uma função-invólucro (= wrapper function). O serviço pesado é
// executado por reachR().
bool 
GRAPHreach( Graph G, vertex s, vertex t) { 
   bool *visited = mallocc( G->V * sizeof (bool));
   for (vertex v = 0; v < G->V; ++v)
      visited[v] = false;
   reachR( G, s, visited);
   bool reachable = visited[t];
   free( visited);
   return reachable;
}

// Imprime (a sequência de vértices do) caminho de s a t armazenado no vetor de
// pais pa[0..G->V-1].
static void 
printPath( Graph G, vertex s, vertex t, vertex *pa) {
   STACKinit( G->V);
   for (vertex w = t; w != s; w = pa[w]) 
      STACKpush( w);
   printf( "%d", s);
   while (!STACKempty( )) 
      printf( "-%d", STACKpop( )); 
   STACKfree( );
}

// Versão recursiva de printPath().
static void 
printPathR( Graph G, vertex s, vertex t, vertex *pa) {
   // o parâmetro G não é usado
   if (s == t)
      printf( "%d", t);
   else {
      printPathR( G, s, pa[t], pa);
      printf( "-%d", t);
   }
}



// Busca em profundidade (= depth-first search = DFS)
////////////////////////////////////////////////////////////////////////////////

// Variáveis globais privadas que serão usadas para a numeração em pré-ordem e
// pós-ordem durante buscas em profundidade (veja função dfsR(), por exemplo).
static int cnt, cntt;
// Esse uso de variáveis globais não é thread-safe, mas simplifica muito o
// código...

// A função privada auxiliar dfsR() é o motor de GRAPHdfs(). Ela recebe um grafo
// G, um vértice v, uma numeração parcial pre[] dos vértices com valores no
// conjunto -1 0 1 ... cnt-1, uma numeração parcial post[] dos vértices com
// valores no conjunto -1 0 1 ... cntt-1, e um vetor de pais parcial pa[]. A
// função faz uma busca DFS em G a partir de v. Se X é o conjunto dos vértices
// acessíveis a partir de v por caminhos que só usam vértices x tais que pre[x]
// vale -1, a função atribui um número pre[x] e um número post[x] a cada x em X.
// Se x é o k-ésimo vértice descoberto então pre[x] recebe o valor cnt + k. Se
// x é o k-ésimo vértices a morrer então post[x] recebe o valor cntt + k. Além
// disso, a função armazena no vetor pa[] a parte da floresta DFS construída
// durante a busca.
static void 
dfsR( Graph G, vertex v, int *pre, int *post, vertex *pa) { 
   pre[v] = cnt++; 
   for (link a = G->adj[v]; a != NULL; a = a->next)
      if (pre[a->w] == -1) {
         pa[a->w] = v; 
         dfsR( G, a->w, pre, post, pa); 
      } 
   post[v] = cntt++;
}

// Esta função-invólucro (= wrapper function) invoca dfsR(). O código foi
// inspirado no programa 18.3 de Sedgewick.
void 
GRAPHdfs( Graph G, int *pre, int *post, vertex *pa) { 
   cnt = cntt = 0; // variáveis globais
   for (vertex v = 0; v < G->V; ++v) 
      pre[v] = post[v] = -1; // A
   for (vertex v = 0; v < G->V; ++v)
      if (pre[v] == -1) {
         pa[v] = v;
         dfsR( G, v, pre, post, pa); // nova etapa
      }
}
// A: Inicializei post[] apenas porque a classificação on-the-fly dos arcos
//    precisa disso.



// Ciclos e dags
////////////////////////////////////////////////////////////////////////////////

// Faz uma busca DFS completa e depois procura um arco de retorno.
bool 
GRAPHcycle0( Graph G) {
   int *pre = mallocc( G->V * sizeof (int));
   int *post = mallocc( G->V * sizeof (int));
   vertex *pa = mallocc( G->V * sizeof (vertex));
   GRAPHdfs( G, pre, post, pa);
   free( pa);
   for (vertex v = 0; v < G->V; ++v) {
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         vertex w = a->w;
         if (post[v] < post[w]) { // v-w é de retorno
            free( post);
            free( pre);
            return true;
         }
      }
   } 
   // post[v] > post[w] para todo arco v-w
   free( post);
   free( pre);
   return false;
}

// Esta função privada auxiliar é usada por GRAPHcycle(). Ela devolve true se
// encontra um ciclo ao percorrer G a partir do vértice v e devolve false em
// caso contrário. O código é inspirado no de dfsR().
static bool 
dfsRcycle( Graph G, vertex v, int *pre, int *post, vertex *pa) { 
   pre[v] = cnt++;
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      vertex w = a->w;
      if (pre[w] == -1) {
         if (dfsRcycle( G, w, pre, post, pa)) return true;
      } else {
         if (post[w] == -1) return true;
      }
   }
   post[v] = cntt++;
   return false;
}

// Esta é uma versão on-the-fly de GRAPHcycle0(). Interrompe a busca DFS tão
// logo encontra um arco de retorno. Esta é uma função-invólucro (= wrapper
// function); o serviço pesado é executado por dfsRcycle(). 
bool 
GRAPHcycle( Graph G) { 
   int *pre = mallocc( G->V * sizeof (int));
   int *post = mallocc( G->V * sizeof (int));
   vertex *pa = mallocc( G->V * sizeof (vertex));
   cnt = cntt = 0; // variáveis globais
   for (vertex v = 0; v < G->V; ++v)
      pre[v] = post[v] = -1;
   bool b = false;
   for (vertex v = 0; v < G->V; ++v)
      if (pre[v] == -1) {
         pa[v] = v;
         b = dfsRcycle( G, v, pre, post, pa);
         if (b) break; // temos um ciclo (não necessariamente passando por v)
      }
   free( pa);
   free( post);
   free( pre);
   return b; 
}

bool 
GRAPHdag( Graph G) {
   return !GRAPHcycle( G);
}



// Componentes conexas (de grafos não-dirigidos)
////////////////////////////////////////////////////////////////////////////////

// Esta função privada auxiliar é usada por UGRAPHconComps(). Ela atribui o
// número id a todos os vértices que estão na componente conexa que contém v. O
// código é uma adaptação de dfsR().
static void 
dfsRconComps( UGraph G, vertex v, int cc[], int id) { 
   cc[v] = id;
   for (link a = G->adj[v]; a != NULL; a = a->next)
      if (cc[a->w] == -1) 
         dfsRconComps( G, a->w, cc, id); 
}

// Esta é uma função-invólucro (= wrapper function). O serviço pesado é
// executado por dfsRconComps(). O código é uma adaptação da busca em
// profundidade GRAPHdfs(). O código foi copiado do programa 18.4, p.100, de
// Sedgewick.
int 
UGRAPHconComps( UGraph G, int cc[]) { 
   int id = 0;
   for (vertex v = 0; v < G->V; ++v) 
      cc[v] = -1;
   for (vertex v = 0; v < G->V; ++v)
      if (cc[v] == -1) 
         dfsRconComps( G, v, cc, id++);
   return id;
}



// Caminhos de comprimento mínimo
////////////////////////////////////////////////////////////////////////////////

// O código foi inspirado no programa 21.6 de Sedgewick.
void 
DAGspt( Dag G, vertex *vv, vertex s, vertex *pa, int *dist) { 
   const int INFINITY = G->V;
   for (vertex v = 0; v < G->V; ++v)
      pa[v] = -1, dist[v] = INFINITY;
   pa[s] = s, dist[s] = 0;

   for (int j = 0; j < G->V; ++j) {
      vertex v = vv[j];
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         vertex w = a->w; 
         if (dist[v] + 1 < dist[w]) {
            dist[w] = dist[v] + 1; // relaxação de v-w
            pa[w] = v;
         }
      }
   }
}



// Busca em largura (= breadth-first search = BFS)
////////////////////////////////////////////////////////////////////////////////

// Função privada auxiliar que implementa o algoritmo de busca em largura. Ela
// visita todos os vértices do grafo G que estão ao alcance do vértice s e
// armazena o vetor de pais da árvore de busca em pa[0..V-1]. A ordem em que os
// vértices são descobertos é registrada no vetor num[0..V-1]. Os vetores num[]
// e pa[] devem ser alocados pelo cliente. (Código inspirado no programa 18.9 de
// Sedgewick.) 
static void 
GRAPHbfs( Graph G, vertex s, int num[], vertex pa[]) { 
   for (vertex v = 0; v < G->V; ++v) 
      num[v] = -1;
   int c = 0;
   num[s] = c++;
   pa[s] = s;
   QUEUEinit( G->V);
   QUEUEput( s); 
   while (!QUEUEempty( )) {
      vertex v = QUEUEget( ); 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         if (num[a->w] == -1) {
            num[a->w] = c++; 
            pa[a->w] = v;
            QUEUEput( a->w); 
         }
   }
   QUEUEfree( ); 
}



// Algoritmo de caminhos mínimos
////////////////////////////////////////////////////////////////////////////////

// Variante da função GRAPHbfs() de busca em largura. O código é inspirado no
// programa 18.9 de Sedgewick.
void 
GRAPHspt( Graph G, vertex s, int dist[], vertex pa[]) { 
   const int INFINITY = G->V; 
   for (vertex v = 0; v < G->V; ++v) 
      dist[v] = INFINITY, pa[v] = -1;
   dist[s] = 0, pa[s] = s;
   QUEUEinit( G->V);
   QUEUEput( s); 
   while (!QUEUEempty( )) {
      vertex v = QUEUEget( ); 
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         vertex w = a->w; 
         if (dist[w] == INFINITY) { 
            dist[w] = dist[v] + 1;
            pa[w] = v;
            QUEUEput( w); 
         }
      }
   }
   QUEUEfree( ); 
}



// Circuitos e florestas (não-radicadas)
////////////////////////////////////////////////////////////////////////////////

// Função privada auxiliar usada por UGRAPHcircuit(). Recebe um grafo G e
// devolve true se encontrar um circuito ao percorrer G a partir do vértice v.
// Inspirada em dfsR().
static bool 
dfsRcircuit( UGraph G, vertex v, int *pre, vertex *pa) { 
   pre[v] = cnt++;
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      vertex w = a->w;
      if (pre[w] == -1) {
         pa[w] = v; 
         if (dfsRcircuit( G, w, pre, pa)) return true;
      } else { // pre[w] < pre[v]
         if (w != pa[v]) return true; 
      }
   }
   return false;
}

// Esta é uma função-invólucro (= wrapper function). O serviço pesado é
// executado pela função privada hasCircuit(). 
bool 
UGRAPHcircuit( UGraph G) {
   int *pre = mallocc( G->V * sizeof (int));
   vertex *pa = mallocc( G->V * sizeof (vertex));
   cnt = 0; // variável global
   for (vertex v = 0; v < G->V; ++v)
      pre[v] = -1;
   for (vertex v = 0; v < G->V; ++v) {
      if (pre[v] == -1) {
         pa[v] = v;
         if (dfsRcircuit( G, v, pre, pa)) {
            free( pre); free( pa);
            return true;
         }
      }
   }
   free( pre); free( pa);
   return false;
}



// Grafos aresta-biconexos (= edge-biconnected)
////////////////////////////////////////////////////////////////////////////////

// Função privada auxiliar usada por UGRAPHebicon(). Calcula lo[v]. Devolve true
// se encontrar uma ponte na subfloresta DFS que tem v como raiz e devolve false
// em caso contrário.
static bool 
dfsRbridge( UGraph G, vertex v, int *pre, vertex *pa, int *lo) {
   vertex w; link a;
   pre[v] = cnt++;
   lo[v] = pre[v];
   for (a = G->adj[v]; a != NULL; a = a->next) {
      w = a->w;
      if (pre[w] != -1) { // v-w é arco de avanço ou de retorno
         if (w != pa[v]) // w é ancestral de pa[v]
            lo[v] = min( lo[v], pre[w]);
      } else { 
         pa[w] = v;
         if (dfsRbridge( G, w, pre, pa, lo)) // calcula lo[w]
            return true;
         if (lo[w] == pre[w]) // v-w é ponte
            return true;       
         lo[v] = min( lo[v], lo[w]) ;
      }
   }
   return false;
}

// Esta é uma função-invólucro (= wrapper function). O serviço pesado é
// executado por dfsRbridge(). Faz uma busca DFS para calcular o lowest preorder
// number lo[] de cada vértice. (Código inspirado no programa 18.7, p.108, de
// Sedgewick.)
bool 
UGRAPHebicon( UGraph G) {
   int *pre = mallocc( G->V * sizeof (int));
   vertex *pa = mallocc( G->V * sizeof (vertex));
   int *lo = mallocc( G->V * sizeof (int));
   // muitos escrevem "low" no lugar do meu "lo"
   bool b = true;
   for (vertex v = 0; v < G->V; ++v)
      pre[v] = -1;
   cnt = 0; // variável global
   pa[0] = 0;
   if (dfsRbridge( G, 0, pre, pa, lo))
      b = false;
   for (vertex v = 1; v < G->V; ++v)
      if (pre[v] == -1) 
         b = false; // G é desconexo
   free( pa);
   free( pre);
   free( lo);
   return b;
}



// Componentes aresta-biconexas (= edge-biconnected components)
////////////////////////////////////////////////////////////////////////////////

// Função privada auxiliar usada por UGRAPHebiconComps(). (Muitos livros
// escrevem "low" no lugar do meu "lo".)
static void 
dfsRebiconComps( UGraph G, vertex v, int *ebc, int *pre, vertex *pa, int *lo, 
   int *pid) {
   pre[v] = cnt++;
   STACKpush( v);
   lo[v] = pre[v];
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      vertex w = a->w;
      if (pre[w] == -1) {
         pa[w] = v;
         dfsRebiconComps( G, w, ebc, pre, pa, lo, pid);
         lo[v] = min( lo[v], lo[w]) ;
      } else { // w á ancestral próprio de v
         if (w != pa[v])
            lo[v] = min( lo[v], pre[w]);
      }
   } 
   if (lo[v] == pre[v]) { // v é cabeça
      vertex u;
      do {
         u = STACKpop( );
         ebc[u] = *pid;
      } while (u != v);
      (*pid)++; 
   }
}

// Implementação on-the-fly do algoritmo de Tarjan para componentes aresta-
// -biconexas. Esta é uma função-invólucro (= wrapper function); o serviço
// pesado é executado por dfsRebiconComps(). 
int UGRAPHebiconComps( UGraph G, int *ebc) {
   int *pre = mallocc( G->V * sizeof (int));
   vertex *pa = mallocc( G->V * sizeof (vertex));
   int *lo = mallocc( G->V * sizeof (int));
   STACKinit( G->V);
   for (vertex v = 0; v < G->V; ++v)
      pre[v] = ebc[v] = -1;
   cnt = 0; // variável global
   int id = 0;
   for (vertex v = 0; v < G->V; ++v)
      if (pre[v] == -1) {
         pa[v] = v;
         dfsRebiconComps( G, v, ebc, pre, pa, lo, &id); // nova etapa
      }
   free( pre); 
   free( lo); 
   free( pa);
   STACKfree( );
   return id;
}



// Grafos fortemente conexos (= strongly connected)
////////////////////////////////////////////////////////////////////////////////

// Função privada auxiliar usada por GRAPHstrongT2(). Faz uma busca em
// profundidade a partir do vértice v e decide se a parte do grafo visitada é
// fortemente conexa. Também calcula lo[v].
static bool 
dfsRstrong( Graph G, vertex v, int *pre, vertex *pa, int *lo) {
   pre[v] = cnt++;
   lo[v] = pre[v];
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      vertex w = a->w;
      if (pre[w] == -1) {
         if (!dfsRstrong( G, w, pre, pa, lo)) // calcula lo[w]
            return false;
         lo[v] = min( lo[v], lo[w]);
      } else if (pre[w] < pre[v]) // v-w é de retorno ou cruzada
         lo[v] = min( lo[v], pre[w]);
   }
   if (lo[v] == pre[v] && pa[v] != v) 
      return false;
   return true;
}

// Versão on-the-fly de GRAPHstrongT1().
bool 
GRAPHstrongT2( Graph G) {
   int *pre = mallocc( G->V * sizeof (int));
   vertex *pa = mallocc( G->V * sizeof (vertex));
   int *lo = mallocc( G->V * sizeof (int));
   for (vertex v = 0; v < G->V; ++v) 
      pre[v] = -1;
   cnt = 0; // variável global
   vertex s = 0;
   if (!dfsRstrong( G, s, pre, pa, lo)) {
      free( pre); free( pa); free( lo);
      return false;
   }
   for (vertex v = 0; v < G->V; ++v) {
      if (pre[v] == -1) {
         free( pre); free( pa); free( lo);
         return false;
      }
   }
   free( pre); free( pa); free( lo);
   return true;
}



// Componentes fortes (= strong components)
////////////////////////////////////////////////////////////////////////////////



// Algoritmo de Tarjan para componentes fortes
////////////////////////////////////////////////////////////////////////////////

// Função privada auxiliar usada em GRAPHstrongCompsT(). (Muitos livros escrevem
// "low" no lugar do meu "lo".)
static void 
dfsRstrongCompsT( Graph G, vertex v, int *sc, int *pre, int *lo, vertex *stack,
   int *t, int *pid) {
   pre[v] = cnt++;
   stack[(*t)++] = v; 
   lo[v] = pre[v];
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      vertex w = a->w;
      if (pre[w] == -1) {
         dfsRstrongCompsT( G, w, sc, pre, lo, stack, t, pid);
         lo[v] = min( lo[v], lo[w]);
      }
      else if (sc[w] == -1) { 
         // w está na pilha stack[0..(*t)-1] 
         lo[v] = min( lo[v], pre[w]);
      }
   }
   // lo[v] is an upper bound on the final, correct, value 
   if (lo[v] == pre[v]) {
      vertex u;
      do { 
         u = stack[--(*t)];
         sc[u] = *pid;
      } while (u != v); 
      (*pid)++;
   }
}

// Esta é uma função-invólucro (= wrapper function). O serviço pesado é
// executado por dfsRstrongCompsT(). A função é uma implementação on-the-fly do
// algoritmo de Tarjan. O código da função é uma versão adaptada da figura 5.15
// do livro "The Design and Analysis of Computer Algorithms" de Ahu, Hopcroft e
// Ullman.
int 
GRAPHstrongCompsT( Graph G, int *sc) {
   int *pre = mallocc( G->V * sizeof (int));
   int *lo = mallocc( G->V * sizeof (int));
   // muitos livros escrevem "low" no lugar do meu "lo"
   vertex *stack = mallocc( G->V * sizeof (vertex));
   for (vertex v = 0; v < G->V; ++v) 
      pre[v] = sc[v] = -1;
   int id = 0;
   int top = 0;
   cnt = 0; // variável global
   for (vertex v = 0; v < G->V; ++v) 
      if (pre[v] == -1)
         dfsRstrongCompsT( G, v, sc, pre, lo, stack, &top, &id);
   free( pre);
   free( lo);
   free( stack);
   return id;
}



// Algoritmo de Kosaraju para componentes fortes
////////////////////////////////////////////////////////////////////////////////


// Função privada auxiliar usada por GRAPHstrongCompsK(). Atribui o rótulo k a
// todo vértice w que está ao alcance de v mas ainda não foi rotulado. Os
// rótulos são armazenados no vetor sc[]; um vértice w é considerado rotulado se
// sc[w] >= 0. 
static void 
dfsRstrongCompsK( Graph G, vertex v, int *sc, int k) { 
   sc[v] = k; 
   for (link a = G->adj[v]; a != NULL; a = a->next)
      if (sc[a->w] == -1) 
         dfsRstrongCompsK( G, a->w, sc, k);
}

// Função privada auxiliar usada por GRAPHstrongCompsK(). Trata-se de versão
// especializada de dfsR(), sem o parâmetro pa[].
static void 
dfsR1( Graph G, vertex v, int *pre, int *post) { 
   pre[v] = cnt++;
   for (link a = G->adj[v]; a != NULL; a = a->next)
      if (pre[a->w] == -1) {
         dfsR1( G, a->w, pre, post); 
      } 
   post[v] = cntt++;
}

// Esta é uma função-invólucro (= wrapper function); o serviço pesado é
// executado por dfsRstrongCompsK() e dfsR1().
int 
GRAPHstrongCompsK( Graph G, int *sc) {
   int k;
   int i; vertex v; 
   Graph GR;
   vertex *vv;
   // fase 1:
   GR = GRAPHreverse( G);
   int *pre = mallocc( G->V * sizeof (int));
   int *post =  mallocc( G->V * sizeof (int));
   cnt = cntt = 0; // variáveis globais
   for (v = 0; v < GR->V; ++v) 
      pre[v] = -1;
   for (v = 0; v < GR->V; ++v) 
      if (pre[v] == -1)
         dfsR1( GR, v, pre, post);
   vv = mallocc( G->V * sizeof (vertex));
   for (v = 0; v < GR->V; ++v) 
      vv[post[v]] = v; // vv[] é uma permutação dos vértices
   GRAPHdestroy( GR);
   free( pre);
   free( post);
   // fase 2:
   for (v = 0; v < G->V; ++v) 
      sc[v] = -1;
   for (k = 0, i = G->V-1; i >= 0; --i) {
      v = vv[i]; // nova etapa
      if (sc[v] == -1) {
         dfsRstrongCompsK( G, v, sc, k);
         k++;
      }
   }
   free( vv);
   return k;
}



// Coloração de vértices
////////////////////////////////////////////////////////////////////////////////

int 
UGRAPHseqColoring( UGraph G, int color[]) { 
   int k = 0;
   for (vertex v = 0; v < G->V; ++v) color[v] = -1;
   bool *available = mallocc( G->V * sizeof (bool));
   for (vertex v = 0; v < G->V; ++v) {
      int c;
      for (c = 0; c < k; ++c) available[c] = true;
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         c = color[a->w];
         if (c != -1) available[c] = false;
      } // available[0..k-1] dá as cores disponíveis para v
      for (c = 0; c < k; ++c) 
         if (available[c]) break;
      color[v] = c;
      if (c == k) k++;
   }
   free( available);
   return k;
}



// Clique máxima
////////////////////////////////////////////////////////////////////////////////



// Grafos bipartidos e circuitos ímpares
////////////////////////////////////////////////////////////////////////////////

// Função privada auxiliar usada por UGRAPHtwoColor().
static bool 
dfsRtwoColor( UGraph G, vertex v, int *color, int c) { 
   color[v] = 1-c;
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      vertex w = a->w; 
      if (color[w] == -1) {
         if (dfsRtwoColor( G, w, color, 1-c) == false) 
            return false; 
      }
      else { // v-w é de avanço ou de retorno
         if (color[w] == 1-c) // base da recursão
            return false;
      }
   }
   return true;
}

// Esta é uma função-invólucro (= wrapper function); o serviço pesado é
// executado por dfsRtwoColor(). Código inspirado no programa 18.6 de Sedgewick.
bool 
UGRAPHtwoColor( UGraph G, int *color) { 
   for (vertex v = 0; v < G->V; ++v) 
      color[v] = -1; // incolor
   for (vertex v = 0; v < G->V; ++v)
      if (color[v] == -1) 
         if (!dfsRtwoColor( G, v, color, 0)) 
            return false;
   return true;
}



// Emparelhamentos (= matchings)
////////////////////////////////////////////////////////////////////////////////

// Função privada auxiliar usada por augmentMatching(). Esta função executa a
// operação M(+)P sobre um emparelhamento M e um caminho aumentador P. O
// emparelhamento M é representado pelo vetor match[0..V-1]. O caminho P é
// representado por um vetor pa[]. O término de P é t. A origem de P não é dada
// explicitamente mas caracterizada pela propriedade pa[s] == s. (Esta função
// vale para qualquer grafo não-dirigido, bipartido ou não.)
static void 
newMatching( vertex *match, vertex t, vertex *pa) { 
   vertex x;
   do {
      x = pa[t];
      match[t] = x;
      match[x] = t; // A
      t = pa[x]; 
   } while (t != x);
}
/* A: a aresta t-x entrou no emparelhamento e a aresta x-pa[x] saiu do
// emparelhamento:
//
//     antes:   .     .     x      depois:   .     x     .
//               \   //\   //\                \   //\   /\\
//                \ //  \ //  \                \ //  \ /  \\
//                 .     .     t                .     t    .
*/



// Emparelhamentos em grafos bipartidos (= bipartite matching)
////////////////////////////////////////////////////////////////////////////////

// Função privada auxiliar usada por UGRAPHbipMatching(). Esta função recebe um
// grafo não-dirigido bipartido G, com bicoloração color[0..V-1], e um
// emparelhamento M representado por match[0..V-1]. A função procura calcular um
// emparelhamento maior que M. Se tiver sucesso, devolve true e modifica match[]
// de acordo. Se fracassar, devolve false sem alterar match[]. A função usa a
// estratégia de busca em largura (BFS). O vetor visited[] é usado para marcar
// os os vértices visitados durante a busca; poderia ter sido alocado e
// desalocado internamente, mas é alocado externamente para permitir o cálculo
// subsequente de uma cobertura mínima. (Esse código não está no livro de
// Sedgewick.) 
static bool 
augmentMatching( UGraph G, int *color, vertex *match, bool *visited) {
   vertex *pa = mallocc( G->V * sizeof (vertex)); 
   for (vertex v = 0; v < G->V; ++v) visited[v] = false;
   QUEUEinit( G->V);
   for (vertex s = 0; s < G->V; ++s) {
      if (color[s] == 0 && match[s] == -1) { 
         visited[s] = true; 
         pa[s] = s;
         QUEUEput( s); 
      }
   }
   // a fila contém todos os vértices solteiros de cor 0
   while (!QUEUEempty( )) { 
      // color[v] == 0 para todo v na fila
      vertex v = QUEUEget( ); 
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         vertex w = a->w; // color[w] == 1
         if (!visited[w]) {
            // v-w não está no emparelhamento
            visited[w] = true; 
            pa[w] = v; 
            if (match[w] == -1) { // caminho aumentador!
               newMatching( match, w, pa);
               QUEUEfree( ); free( pa);
               return true;
            }
            vertex x = match[w]; // color[x] == 0 e visited[x] == false
            visited[x] = true;
            pa[x] = w; // caminho ganhou segmento v-w-x
            QUEUEput( x); 
         }
      }
   }
   QUEUEfree( ); free( pa);
   return false;
}
// O processo iterativo é uma busca em largura que procura por um caminho
// alternante simples, de comprimento maior que 0, que comece num vértice
// solteiro de cor 0 e termine num vértice solteiro de cor 1. Em caso de
// sucesso, o caminho é armazenado no vetor de pais pa[].

// Esta é uma função-invólucro (= wrapper function); o serviço pesado é
// executado por augmentMatching(). A função usa busca BFS para procurar
// caminhos aumentadores. (Esta função não está no livro de Sedgewick.)
int 
UGRAPHbipMatching( UGraph G, int *color, vertex *match, bool *cover) {
   bool *visited = mallocc( G->V * sizeof (bool));
   for (vertex v = 0; v < G->V; ++v) match[v] = -1;
   int size = 0;
   while (augmentMatching( G, color, match, visited))
      size++;
   for (vertex v = 0; v < G->V; ++v) {
      if ((color[v] == 1 && visited[v]) || (color[v] == 0 && !visited[v]))
         // superfluous parentheses to make compiler happy
         cover[v] = true;
      else cover[v] = false;
   }
   free( visited);
   return size;
}



// Algoritmo de Prim para árvores geradoras de custo mínimo (= MST = minimal
// spanning tree)
////////////////////////////////////////////////////////////////////////////////

// Versão ingênua. Tempo V*E.
int 
UGRAPHmstP0( UGraph G, vertex pa[]) { 
   const int INFINITY = INT_MAX;
   for (vertex w = 0; w < G->V; ++w) pa[w] = -1; 
   vertex s = 0;
   pa[s] = s; 
   int mstcost = 0;
   while (true) {
      int minc = INFINITY;
      vertex x = 0, y = 0;
      for (vertex v = 0; v < G->V; ++v) {
         if (pa[v] == -1) continue; 
         for (link a = G->adj[v]; a != NULL; a = a->next) 
            if (pa[a->w] == -1 && a->c < minc) {
               minc = a->c;
               x = v, y = a->w;
            }
      }   
      if (minc == INFINITY) break; 
      pa[y] = x;
      mstcost += minc;
   }
   return mstcost;
}

// O código é uma versão melhorada do Programa 20.3 de Sedgewick.
int
UGRAPHmstP1( UGraph G, vertex pa[]) {  
   const int INFINITY = INT_MAX;
   bool *tree = mallocc( G->V * sizeof (bool));
   vertex *preco = mallocc( G->V * sizeof (int)); // price
   // inicialização:
   for (vertex v = 0; v < G->V; ++v) 
      pa[v] = -1, tree[v] = false, preco[v] = INFINITY; 
   pa[0] = 0, tree[0] = true;
   for (link a = G->adj[0]; a != NULL; a = a->next) {
      pa[a->w] = 0, preco[a->w] = a->c; 
   }
   int mstcost = 0;
   while (true) { 
      int minc = INFINITY;
      vertex y = 0; // y is initialized just to make compiler happy 
      for (vertex w = 0; w < G->V; ++w) {
         if (!tree[w] && preco[w] < minc) 
            minc = preco[w], y = w; 
      }
      if (minc == INFINITY) break;
      // aresta pa[y]-y é a mais barata da franja
      tree[y] = true; 
      mstcost += preco[y];
      // atualização de preco[]:
      for (link a = G->adj[y]; a != NULL; a = a->next) {
         vertex w = a->w;
         int c = a->c;
         if (!tree[w] && c < preco[w]) {
            preco[w] = c; 
            pa[w] = y; 
         }
      }
   }
   free( tree); free( preco);
   return mstcost;
}

// Código inspirado no Programa 21.1 de Sedgewick.
int
UGRAPHmstP2( UGraph G, vertex pa[]) { 
   const int INFINITY = INT_MAX;
   bool *tree = mallocc( G->V * sizeof (bool));
   vertex *preco = mallocc( G->V * sizeof (int)); // price
   // inicialização:
   for (vertex v = 1; v < G->V; ++v) 
      pa[v] = -1, tree[v] = false, preco[v] = INFINITY; 
   pa[0] = 0, tree[0] = true;
   for (link a = G->adj[0]; a != NULL; a = a->next) {
      pa[a->w] = 0; 
      preco[a->w] = a->c; 
   } 
   PQinit( G->V); 
   for (vertex v = 1; v < G->V; ++v)
      PQinsert( v, preco); 
   int mstcost = 0;
   while (!PQempty( )) {
      vertex y = PQdelmin( preco);
      if (preco[y] == INFINITY) break; // supérfluo se G conexo
      tree[y] = true;
      mstcost += preco[y];
      // atualização de preco[]:
      for (link a = G->adj[y]; a != NULL; a = a->next) {
         vertex w = a->w; 
         int c = a->c;
         if (!tree[w] && c < preco[w]) { 
            preco[w] = c; 
            PQdec( w, preco); 
            pa[w] = y;
         }
      }
   }
   PQfree( ); free( tree); free( preco);
   return mstcost;
}



// Algoritmo de Kruskal para árvores geradoras de custo mínimo (= MST = minimal
// spanning tree)
////////////////////////////////////////////////////////////////////////////////


// Implementação ingênua do algoritmo de Kruskal, sem union-find.
int 
UGRAPHmstK0( UGraph G, edge mst[]) { 
   vertex *chefe = mallocc(G->V * sizeof (vertex));
   for (vertex v = 0; v < G->V; ++v) 
      chefe[v] = v;
   int k = 0;
   const int INFINITY = INT_MAX;
   int mstcost = 0;
   while (true) {
      // a floresta tem arestas mst[0..k-1]
      int minc = INFINITY;
      vertex x, y;
      for (vertex v = 0; v < G->V; ++v) {
         for (link a = G->adj[v]; a != NULL; a = a->next) {
            vertex w = a->w; int c = a->c;
            if (v < w && chefe[v] != chefe[w] && c < minc) {
               minc = c;
               x = v, y = w;
            }
         }
      }
      if (minc == INFINITY) return mstcost;
      edge e; e.v = x, e.w = y, e.c = minc; 
      mstcost += e.c;
      mst[k++] = e;
      vertex v0 = chefe[x], w0 = chefe[y];
      for (vertex v = 0; v < G->V; ++v)
         if (chefe[v] == w0)
            chefe[v] = v0;
   }
   free( chefe);
}

// Esta função privada auxiliar compara o campo c de dois objetos *aa e *bb do
// tipo edge. A função é usada como 3-o argumento da função qsort() da
// biblioteca stdlib. Para ordenar um vetor arr[0..N-1] de objetos do tipo edge,
// diga qsort( arr, N, sizeof (edge), compareEdges).
static int 
compareEdges( const void *aa, const void *bb) {
    edge *a = (edge *) aa;
    edge *b = (edge *) bb;
    if (a->c < b->c) return -1;
    if (a->c > b->c) return  1;
    return 0;
}

// Implementação eficiente do algoritmo de Kruskal. Usa union-find. Consome
// V*(E+V) log^* V unidades de tempo no pior caso. Usa a função auxiliar
// compareEdges(). (O código foi copiado, com ligeiras modificações, do
// Programa 20.5, p.249, de Sedgewick.) 
int 
UGRAPHmstK1( UGraph G, edge mst[]) { 
   // typedef struct {vertex v, w;} edge; // definido em GRAPHlist.h
   int V = G->V;
   edge *e = mallocc( (V*(V-1)/2) * sizeof (edge));  
   UGRAPHedges( G, e);
   int E = G->A/2; 
   // quickSort( e, 0, E-1); 
   qsort( e, E, sizeof (edge), compareEdges);
   UFinit( V);
   int mstcost = 0;
   int k = 0;
   for (int i = 0; k < V-1; ++i) {
      vertex v0 = UFfind( e[i].v);
      vertex w0 = UFfind( e[i].w);
      if (v0 != w0) {
         UFunion( v0, w0);
         mst[k++] = e[i];
         mstcost += e[i].c;
      }
   }
   // mst[0..V-2] é o conjunto de arestas de uma MST
   UFfree( ); free( e);
   return mstcost;
} 



// Caminhos de custo mínimo (CPT)
////////////////////////////////////////////////////////////////////////////////

// CPT = cheapest-paths tree = árvore de caminhos de custo mínimo.

// Os custos nos arcos são arbitrários (positivos e negativos).



// Algoritmo de Bellman-Ford para caminhos mínimos 
////////////////////////////////////////////////////////////////////////////////

// Esta é a implementação "queue-based", ou "FIFO-based", do algoritmo de
// Bellman-Ford. Código inspirado no Programa 21.9 de Sedgewick.
vertex
GRAPHcptBF( Graph G, vertex s, vertex *pa, int *dist) { 
   const int INFINITY = INT_MAX;
   QUEUEinit( G->A);
   bool *onqueue = mallocc( G->V * sizeof (bool));
   for (vertex u = 0; u < G->V; ++u)
      pa[u] = -1, dist[u] = INFINITY, onqueue[u] = false;
   pa[s] = s, dist[s] = 0;
   QUEUEput( s);
   onqueue[s] = true;
   vertex V = G->V; // pseudovértice
   QUEUEput( V); // sentinela
   int k = 0;
   while (true) {
      vertex v = QUEUEget( );
      if (v < V) {
         for (link a = G->adj[v]; a != NULL; a = a->next) {
            if (dist[v] + a->c < dist[a->w]) {
               dist[a->w] = dist[v] + a->c; // relaxação do arco a
               pa[a->w] = v;
               if (onqueue[a->w] == false) {
                  QUEUEput( a->w);
                  onqueue[a->w] = true;
               }
            }
         }
      } else { 
         if (QUEUEempty( )) {
            QUEUEfree( );
            free( onqueue);
            return -1; // não há ciclo negativo e pa[] representa CPT
         }
         if (++k >= G->V) break; // há ciclo negativo 
         QUEUEput( V); // sentinela na fila
         for (vertex u = 0; u < G->V; ++u) onqueue[u] = false;
      }
   }
   free( onqueue);
   // procura ciclo negativo:
   while (true) {
      vertex z = QUEUEget( ); // é possível que nenhum z-w esteja tenso
      for (link a = G->adj[z]; a != NULL; a = a->next) {
         if (dist[z] + a->c < dist[a->w]) { // arco z-w está tenso
            QUEUEfree( );
            bool *visited = mallocc( G->V * sizeof (bool));
            for (vertex u = 0; u < G->V; ++u) visited[u] = false;
            while (!visited[z]) {
               visited[z] = true;
               z = pa[z];
            } // z-pa[z]-pa[pa[z]]-...-z é um ciclo negativo
            free( visited);
            return z;
         }
      }
   }
}



// Caminhos baratos em dags (custos arbitrários)
////////////////////////////////////////////////////////////////////////////////

// O código foi inspirado no programa 21.6 de Sedgewick.
void 
DAGcpt( Dag G, vertex *vv, vertex s, vertex *pa, int *dist) { 
   const int INFINITY = INT_MAX;
   for (vertex v = 0; v < G->V; ++v)
      pa[v] = -1, dist[v] = INFINITY;
   pa[s] = s, dist[s] = 0;
   for (int j = 0; j < G->V; ++j) {
      vertex v = vv[j];
      if (dist[v] == INFINITY) continue;
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         if (!(dist[v] + a->c >= dist[a->w])) {
            dist[a->w] = dist[v] + a->c; 
            pa[a->w] = v;
         }
      }
   }
}



// Algoritmo de Dijkstra para caminhos mínimos sob custos positivos
////////////////////////////////////////////////////////////////////////////////

// Implementação ingênua. Consome V*A unidades de tempo. Vamos supor que INT_MAX
// é maior que o custo de qualquer caminho simples com origem s.
void 
GRAPHcptD0( Graph G, vertex s, vertex *pa, int *dist) { 
   const int INFINITY = INT_MAX;
   for (vertex v = 0; v < G->V; ++v) 
      pa[v] = -1, dist[v] = INFINITY;
   pa[s] = s, dist[s] = 0; 
   while (true) {
      int minc = INFINITY;
      vertex x = 0, y = 0;
      // x e y inicializados apenas para que o compilador não reclame 
      for (vertex v = 0; v < G->V; ++v) {
         if (pa[v] == -1) continue;
         for (link a = G->adj[v]; a != NULL; a = a->next) {
            if (pa[a->w] != -1) continue;
            if (dist[v] + a->c < minc) {
               minc = dist[v] + a->c;
               x = v, y = a->w;
            }
         }
      }
      if (minc == INFINITY) break; 
      pa[y] = x, dist[y] = minc;
   }
}

// Código inspirado no Programa 20.3 de Sedgewick. Não usa fila priorizada.
void 
GRAPHcptD1( Graph G, vertex s, vertex *pa, int *dist) {
   const int INFINITY = INT_MAX;
   bool *tree = mallocc( G->V * sizeof (bool));
   // inicialização:
   for (vertex v = 0; v < G->V; ++v)
      pa[v] = -1, tree[v] = false, dist[v] = INFINITY;
   pa[s] = s, tree[s] = true, dist[s] = 0;
   for (link a = G->adj[s]; a != NULL; a = a->next) 
      pa[a->w] = s, dist[a->w] = a->c;
   while (true) {
      // escolha de y:
      int minc = INFINITY;
      vertex y = 0; // y initialized to make compiler happy
      for (vertex z = 0; z < G->V; ++z) {
         if (tree[z]) continue;
         if (dist[z] < minc) // dist[z] é o preço de z
            minc = dist[z], y = z;
      }
      if (minc == INFINITY) break;
      // atualização de dist[]:
      for (link a = G->adj[y]; a != NULL; a = a->next) {
         vertex w = a->w;
         if (tree[w]) continue;
         int c = a->c;
         if (dist[y] + c < dist[w]) {
            dist[w] = dist[y] + c; // relaxação de y-w
            pa[w] = y;
         }
      }
      tree[y] = true;
   }
   free( tree);
}

// Código inspirado no Programa 21.1 de Sedgewick. Usa uma fila priorizada.
void 
GRAPHcptD2( Graph G, vertex s, vertex *pa, int *dist) {
   const int INFINITY = INT_MAX;
   bool *mature = mallocc( G->V * sizeof (bool));
   for (vertex v = 0; v < G->V; ++v)
      pa[v] = -1, mature[v] = false, dist[v] = INFINITY; 
   pa[s] = s, dist[s] = 0;
   PQinit( G->V);
   for (vertex v = 0; v < G->V; ++v) PQinsert( v, dist);
   while (!PQempty( )) {
      vertex y = PQdelmin( dist);
      if (dist[y] == INFINITY) break;
      mature[y] = true;
      // atualização de dist[]:
      for (link a = G->adj[y]; a != NULL; a = a->next) {
         vertex w = a->w;
         if (mature[w]) continue;
         int c = a->c;
         if (dist[y] + c < dist[w]) {
            dist[w] = dist[y] + c; // relaxa y-w
            PQdec( w, dist);
            pa[w] = y;
         }
      }
   }
   PQfree( ); free( mature);
}



// Caminhos de comprimento máximo (= longest path) e de custo máximo
////////////////////////////////////////////////////////////////////////////////

// Esta é uma função privada auxiliar usada por GRAPHmaxCostPath(). A função
// recebe um grafo G com custos positivos nos arcos, um conjunto de vértices
// marcados, e vértices não marcados v e t (possivelmente iguais). A função
// examina o conjunto, digamos C, de todos os caminhos simples de v a t que não
// têm vértices marcados. Se C é vazio, devolve -1. Senão, devolve o custo do
// caminho mais caro de C. (Em particular, devolve 0 se v == t.)  A função NÃO
// ALTERA o conjunto de vértices marcados. 
static int 
dfsRmaxCostPath( Graph G, vertex v, vertex t, bool *mark) {
   if (v == t) return 0;
   mark[v] = true;
   int m = -1;
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      if (!mark[a->w]) {
         int mw = dfsRmaxCostPath( G, a->w, t, mark);
         if (mw != -1 && a->c + mw > m) 
            m = a->c + mw;
      }
   }
   mark[v] = false; // backtrack!
   return m;
}

// Esta é uma função-invólucro (= wrapper function); o serviço pesado é
// executado por dfsRmaxCostPath(). O código foi inspirado no programa 17.12
// de Sedgewick.
int 
GRAPHmaxCostPath( Graph G, vertex s, vertex t) {
   bool *mark = mallocc( G->V * sizeof (bool));
   for (vertex v = 0; v < G->V; ++v) mark[v] = false;
   int cost = dfsRmaxCostPath( G, s, t, mark);
   free( mark);
   return cost;
}



// Fluxo máximo (max flow)
////////////////////////////////////////////////////////////////////////////////

Graph 
GRAPHinputArcsFlow( FILE *infile, int *ps, int *pt) {
   int V, A;
   fscanf( infile, "%d %d", &V, &A);
   Graph G = GRAPHinit( V);
   fscanf( infile, "%d %d", ps, pt); // única diferença em relação a 
                                     // GRAPHinputArcs_c()
   for (int i = 0; i < A; ++i) {
      vertex v, w; 
      int c; // capacidade do arco v-w
      fscanf( infile, "%d-%d %d", &v, &w, &c); 
      GRAPHinsertArc_c( G, v, w, c);
   }
   // invertLists_i( G);
   return G;
}

int 
GRAPHflowIntensity( Graph G, vertex s) {
   int intens = 0;
   for (link a = G->adj[s]; a != NULL; a = a->next) 
      intens += a->flow;
   for (vertex v = 0; v < G->V; ++v)
      for (link a = G->adj[v]; a != NULL; a = a->next) 
         if (a->w == s) intens -= a->flow;
   return intens;
}

// Esta é uma função auxiliar usada por GRAPHmaxFlow(). Ela acrescenta arcos
// artificiais ao grafo G e preenche os campos type e twin de todos os nós das
// listas adj[].
static void 
expandGraph( Graph G) { 
   for (vertex v = 0; v < G->V; ++v) 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         a->type = +1;
   for (vertex v = 0; v < G->V; ++v) 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         if (a->type == +1) {
            link b = malloc( sizeof (struct node));
            b->w = v; 
            b->c = 0; 
            b->type = -1; 
            b->twin = a;
            a->twin = b;
            b->next = G->adj[a->w];     
            G->adj[a->w] = b;
         }
}

// Esta é uma função auxiliar usada por GRAPHmaxFlow1() e GRAPHmaxFlow2(). Ela
// desfaz o efeito de expandGraph(), removendo todos os arcos artificiais do
// grafo. (A função supõe que os nós que representam os arcos artificiais estão
// concentrados no início das listas adj[].)
static void 
contractGraph( Graph G) {
   for (vertex v = 0; v < G->V; ++v) {
      link a = G->adj[v];
      while (a != NULL && a->type == -1) {
         link b = a;
         G->adj[v] = a = a->next;
         free( b);
      }
   }
}

// Esta função recebe um grafo capacitado G e um fluxo (registrado nos campos
// flow dos nós das listas de adjacência). Calcula um caminho de comprimento
// (número de arcos) mínimo de s a t dentre os que têm capacidade residual
// estritamente positiva e devolve a capacidade residual do caminho. Além disso,
// armazena o caminho nos vetores pa[] e parc[]. Se nenhum caminho de s a t tem
// capacidade residual estritamente positiva, devolve 0 e armazena no vetor
// visited[] o vetor característico da margem superior de um corte de capacidade
// mínima dentre os que separam s de t. A função supõe que todos os arcos têm
// capacidade menor que a constante MCAP. 
static int 
ShrtAugmPath( Graph G, vertex s, vertex t, vertex pa[], link parc[],
   bool visited[]) {
   for (vertex v = 0; v < G->V; ++v) visited[v] = false; 
   QUEUEinit( G->V); 
   visited[s] = true;
   QUEUEput( s); 
   while (!QUEUEempty( )) {
      vertex v = QUEUEget( );
      if (v == t) break;
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         vertex w = a->w;
         int residual = a->c - a->flow; 
         // a pode ser original ou artificial
         if (residual > 0 && !visited[w]) {
            visited[w] = true;
            pa[w] = v; parc[w] = a; 
            QUEUEput( w); 
         }
      }
   }
   if (!visited[t]) return 0; 
   int delta = MCAP;
   for (vertex w = t; w != s; w = pa[w]) { 
      link a = parc[w]; 
      delta = min( delta, a->c - a->flow);
   }
   if (DEBUG) printAugmPath( G, s, t, pa, parc, delta);
   QUEUEfree( );
   return delta;
}

// Esta função recebe um grafo capacitado G e um fluxo (registrado nos campos
// flow dos nós das listas de adjacência). Calcula um caminho de capacidade
// residual máxima de s a t dentre os que têm capacidade residual estritamente
// positiva e devolve a capacidade residual do caminho. Além disso, armazena o
// caminho nos vetores pa[] e parc[]. Se nenhum caminho de s a t tem capacidade
// residual estritamente positiva, devolve 0 e armazena no vetor visited[] o
// vetor característico da margem superior de um corte de capacidade mínima
// dentre os que separam s de t. A função supõe que todos os arcos têm
// capacidade menor que a constante MCAP. 
static int 
MaxCapAugmPath( Graph G, vertex s, vertex t, vertex pa[], link parc[],
   bool visited[]) {
   int *cprd = mallocc( G->V * sizeof (int));
   maxPQinit( G->V); 
   for (vertex x = 0; x < G->V; ++x)
      cprd[x] = 0, maxPQinsert( x, cprd); 
   cprd[s] = MCAP; 
   maxPQinc( s, cprd); 
   while (!maxPQempty( )) {
      vertex x = maxPQdelmax( cprd);
      if (cprd[x] == 0 || x == t) break;
      for (link a = G->adj[x]; a != NULL; a = a->next) {
         int residual = min( a->c - a->flow, cprd[x]);
         if (residual > cprd[a->w]) { 
            cprd[a->w] = residual; 
            pa[a->w] = x, parc[a->w] = a; 
            maxPQinc( a->w, cprd); 
         }
      }
   }
   maxPQfree( );
   int delta = cprd[t];
   if (DEBUG && delta > 0)
      printAugmPath( G, s, t, pa, parc, delta);
   for (vertex v = 0; v < G->V; ++v) 
      if (cprd[v] > 0) visited[v] = true; 
      else visited[v] = false; 
   free( cprd);   
   return delta;
}

// Idêntico a GRAPHmaxFlow2() exceto pela chamada de MaxCapAugmPath(), que é
// trocada por uma chamada de ShrtAugmPath(). (Código inspirado na segunda parte
// do programa 22.3 de Sedgewick.)
int 
GRAPHmaxFlow1( Graph G, vertex s, vertex t, bool visited[]) { 
   vertex *pa = mallocc( G->V * sizeof (vertex)); // parent vertex
   link *parc = mallocc( G->V * sizeof (link)); // parent arc
   expandGraph( G);
   for (vertex v = 0; v < G->V; ++v) 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         a->flow = 0;
   int numaugmentations = 0;
   int intensity = 0;
   while (true) {
      int delta = ShrtAugmPath( G, s, t, pa, parc, visited);
      if (delta == 0) break;
      for (vertex w = t; w != s; w = pa[w]) { 
         link a = parc[w]; 
         a->flow += delta; 
         a->twin->flow -= delta; 
      }
      intensity += delta;
      ++numaugmentations;
   }
   contractGraph( G);
   free( pa);
   free( parc);
   if (DEBUG) printf( "   %d augmentations\n", numaugmentations); 
   return intensity;
}

// Idêntico a GRAPHmaxFlow1() exceto pela chamada de ShrtAugmPath(), que é
// trocada por uma chamada de MaxCapAugmPath(). (Código inspirado na segunda
// parte do programa 22.3 de Sedgewick.)
int 
GRAPHmaxFlow2( Graph G, vertex s, vertex t, bool visited[]) { 
   vertex *pa = mallocc( G->V * sizeof (vertex)); // parent vertex
   link *parc = mallocc( G->V * sizeof (link)); // parent arc
   expandGraph( G);
   for (vertex v = 0; v < G->V; ++v) 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         a->flow = 0;
   int numaugmentations = 0;
   int intensity = 0;
   while (true) {
      int delta = MaxCapAugmPath( G, s, t, pa, parc, visited);
      if (delta == 0) break;
      for (vertex w = t; w != s; w = pa[w]) { 
         link a = parc[w]; 
         a->flow += delta; 
         a->twin->flow -= delta; 
      }
      intensity += delta;
      ++numaugmentations;
   }
   contractGraph( G);
   free( pa);
   free( parc);
   if (DEBUG) printf( "   %d augmentations\n", numaugmentations); 
   return intensity;
}

////////////////////////////////////////////////////////////////////////////////