Let G=(V, E) directed graph. Let v be a vertex in G, find the number of vertices that take part in non-simple directed paths to v

Question

Let G=(V, E) directed graph.

Let v be a vertex in G, find the number of vertices that take part in non-simple directed paths to v.

My attempt:

1. Find strongly connected components , V_1,V_2...,V_i (using DFS search produces).

2. Perform topological sorting on the V_1,V_2...,V_i.

3. Suppose v in V_j. Perform DFS on V_1 to V_j and count all vertex in the strongly connected components whose size is bigger than 1.

Is my solution correct?

Answer 1

First step: check your graph for cycles. It there are none, then there are no non-simple paths..

Second: check your graph for component count. If there is 1 component then the number of vertices that take part in non-simple directed paths is equal to the number of vertices in the graph, because every vertex can go to a vertex in a cycle, go around the cycle, and continue to the destination.

Third: Check the component that contains v for cycles. It there are none, then there are no non-simple paths. Otherwise the number of vertices that take part in non-simple directed paths is equal to the number of vertices in the component.