Enunciado do exercício |  Índice remissivo

Cálculo ineficiente do vetor low[ ]

static int conta, lbl[1000], low[1000];
static Vertex parent[1000];

/* Esta função faz uma busca em profundidade no grafo G 
   e imprime lbl[v] e low[v] para cada vértice v do grafo.
*/

void compute_low (Graph G) { 
   Vertex v, w;
   conta = 0;
   for (v = 0; v < G->V; v++) 
      lbl[v] = -1;
   for (v = 0; v < G->V; v++)
      if (lbl[v] == -1) 
         dfsR(G, EDGE(v, v));

   for (w = 0; w < G->V; w++) 
      low[w] = lbl[w];
   for (w = 1; w < G->V; w++) {
      link t;
      for (t = G->adj[w]; t != NULL; t = t->next) {
         v = t->w;
         if (lbl[v] < lbl[w] && v != parent[w]) { 
            Vertex i = w;
            while (low[i] > lbl[v]) {
               low[i] = lbl[v];
               i = parent[i];
            }
         }
      }
   }

   print(G->V);
}


void dfsR (Graph G, Edge e) { 
   link t; 
   Vertex w = e.w;
   lbl[w] = conta++; 
   parent[w] = e.v;
   for (t = G->adj[w]; t != NULL; t = t->next) 
      if (lbl[t->w] == -1) 
         dfsR(G, EDGE(w, t->w)); 
}


void print (int V) {
   Vertex v;
   printf("\n   v lbl[v] low[v]\n");
   for (v = 0; v < V; v++) 
      printf("%4d %6d %6d\n", v, lbl[v], low[v]);
   printf("\n");
}