I am curious of knowing of an efficient algorithm for the problem:
Given two vertices s,t in a directed graph, is there a vertex x such that
I can of course do a BFS from each node of the graph resulting in a quadratic time algorithm.
Or I can reverse all the edges of the graph, do a BFS from
s store all reachable vertices in a hashtable, do a BFS from
t and check for each reachable vertex if it is in the table, ifso, I found
x. While the running time is linear, the extra space requirement is ugly.
Is there any elegant O(E + V) time algorithm for this problem?