SCC

DFS(G) is given below.

1. Complete the table for G.

   G	a	b	c	d	e	f	g	h
   d	1	2	3	5	8	9	13	14
   f	12	7	4	6	11	10	16	15
   p	NIL	a	b	c	a	e	NIL	g

2. Give f[u] in decreasing order. g,h,a,e,f,b,d,c
3. Draw G^T.
4. Find DFS(G^T), in the main loop of DFS consider the vertices in order of decreasing f[u]. Assume that the adjacency list is ordered alphabetically. Show the discovery and finishing times for each vertex (d on the left and f on the right side of the node).

   GT	a	b	c	d	e	f	g	h
   d	5	7	6	9	10	12	1	3
   f	16	8	15	14	11	13	2	4
   p	NIL	c	a	c	d	e	NIL	NIL

5. On the graph above, circle G^SCC

G^SCC