Suppose we perform Depth First Search (DFS) on a digraph G=(V,E)

given by its adjacency list structure and label each node uV

by d[u]

and f[u]

, indicating the starting and finishing times of DFSvisit(u), as we learned in the course.

Consider an arbitrary pair of distinct vertices u

and v

such that there is a directed path from u

to v

in G

. Then that implies

(If more than one choice is correct, select the red choice.)

Question 2Answer

a.

d[u]

.

b.

None of the other choices.

c.

f[u]>f[v]

.

d.

More than one of the other choices are correct.

e.

d[u]

.