CODEWITHSUNDEEP
algorithmgraphdepth-first-search
Stratford
Stratford

Reputation: 323

Modifications of BFS/DFS to check simple paths

I have to design an algorithm as from BFS or DFS to do the following, given G=(V,E) a directed graph:

Check whether there is at most one simple path from s to any other vertex u in V. This algorithm has to be on O(|V|+|E|).

And from the previous algorithm, I have to design another one O(|V||E|) algorithm to check whether there is at most one simple path between any two vertices u and v.

I hope you can help me! Thanks a lot in advance!

Upvotes: 0

Views: 844

Answers (1)

Fallen
Fallen

Reputation: 4565

Hint: What if all the edges on the path from s to u are cut edges (bridge)? What if any of them are not cut edge? :)

Note: We can find all the bridges in a graph O(V+E) time

Upvotes: 2

Related Questions