Exercises 22.1-8

It can check edge in the graph in O(1) time, but it wastes space. We can use tree instead of hash table, tree’s search can be done in O(lg n) time.

Exercises 22.1-7

= degree of i, if i = j or -# edges of ij, otherwise.

Exercises 22.1-6

Start from one node u, if there is one edge (u,v), then u is not sink. If there is no edge (u,v), then v is not sink. Since checking one edge can reduce the candidates by one. We can check at most O(V) edges and find the sink.

Exercises 22.1-5

Adjacency matrix: Given the matrix A, then A’s square is the solution. Time complexity is .

Adjacency list: In graph G if node u is adjacent to v, then v’s neighbors will become u’s neighbors. Hence we can replace v with v’s neighbors into u’s neighbor. The running time is O(EV).

Exercises 22.1-4

Like DFS, we construct a DFS tree and record all tree edges and back edges. Then E’ = tree edges + back edges. The running time is O(V+E).

Exercises 22.1-3

Brute Force.

Matrix: .
List: O(|E|).

Exercises 22.1-2

Exercises 22.1-1

O(|E| + |V|).