Step 0
: If there is no path from v to t, then answer is NO.
Step 1
: Make the graph G' after collapsing all the strongly connected components of G.
Step 2
: If the vertex 'v' is a part of some SCC consisting of more than 1 vertex, then there definitely exists a non-simple path. Similarly if vertex 't' is a part of some SCC consisting of more than 1 vertex then answer is YES.
Step 3
: If step2 is not true. Then determine if there exists any path from v to t in graph G' that goes through a vertex that was collapsed into a strongly connected component of 2 or more vertices. If so, then answer is YES else the answer is NO.
Running Time: O(M+N) for each of the steps in the above algorithm. Thus overall O(M+N)
.
Edit: On how to do step 3 in linear time:
For every vertex in G', maintain two things:
- Size of that vertex. (No. of vertices of G that were contracted for this SCC vertex)
- Is this vertex reachable from t or not. (We can compute this by running dfs from t on the reverse graph of G')
Now the following function throughSCC(int vertex) will return true if there exists a path from the vertex 'vertex' in G' to the vertex t that goes through any SCC vertex of size >= 2. Pseudocode for the function:
boolean throughSCC(int vertex){
if(!reachable[vertex]){
return false;
}
if(sz[vertex] >= 2){
return true;
}
for(all neighbours X of vertex){
if(throughSCC(X)){
return true;
}
}
return false;
}