Exercises 22.3-12

Solution 1:
For each vertex v, construct DFS tree T rooted from v. Check whether T has forward or cross edge. If every T has no forward or cross edge, then G is singly connected.  Time complexity is O(V(V+E)).

Exercises 22.3-11

Let F be the DFS forest, if u and v are in the same tree, then u and v are in the same connected component.

Exercises 22.3-10

Let G=(V,E), V={u,v,w}, E={<v,u>,<u,w>}.

Exercises 22.3-9

Exercises 22.3-8

The same as exercises 22.3-7.

Exercises 22.3-7

Let G=(V,E). V = {u, v, w}, E={<w,u>, <w,v>, <u,w>}. The dfs tree = {<w,u>,<w,v>}, which w is the root.

Exercises 22.3-6

Modify the DFS-Visit(u) line 4~7 as follows.

Push u into stack S
While S is not empty
    u = pop from S
    for each v ∈ Adj[u]
        do if color[v] = WHITE
            then π[v] = u
            Push v into S

Exercises 22.3-5

Since the graph is undirected, if u is encountered firstly, then edge (u,v) is tree edge. If v is encountered firstly, edge (v,u) will be tree edge.

Exercises 22.3-4

By the parenthesis structure, it is easy to prove.

Exercises 22.3-3