Page 332, Exercise 9

 

void bridge(int u, int v)

{/* Modified version of bicon to determine

 the bridges.

 compute dfn and low, and output the edges of G by their

biconnected components, v is the parent (if any) of the spanning

tree of u.  dfn[0] to dfn[MAX_SIZE] is initialized to -1, and

num is set to 0 before the function begins */

   NodePointer ptr;

   int w,x,y;

   dfn[u] = low[u] = num++;

   for (ptr = graph[u]; ptr; ptr = ptr->link)  {

      w = ptr->vertex;

	  if (dfn[w] == 0) 

	  {/* if the node hasn't been examined call brige with it */

         bridge(w,u);

		 low[u] = MIN2(low[u], low[w]);

		 if (low[w] > dfn[u])

		 /*{if the low value of node w is greater than the depth

            first search value of u, then  is a bridge*/

                printf("%d, %d\n", w, u);

      else if (w!= u)

	  /* determine if the low value of u needs to be adjusted */

	     low[u] = MIN2(low[u], dfn[w]);

	 }

	}

}