I'm on a search for the most simple algorithm that could tell (returns true or false) if there is a NON-SIMPLE path between vertex v and t given a directed graph.

I don't mind using BFS, DFS, Dijkstra or any other algorithm that could help solving this problem, I was trying to get the SCC graph, but I couldn't find any good use to it.

Any help would be appreciated!

Thank you!

# Best How To :

`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;
}
```