Problem Detail: Or in other words, find all $v in V$ such that there exists a path $forall w in V$ $v rightarrow w$ or $w rightarrow v$. This is for a directed acyclic graph. I need to find an $O(|E| + |V|)$ algorithm for this. I can see how to identify if a given vertex meets these traits (perform a BFS starting at that vertex, then do another BFS on the reverse of that graph and see if every vertex was visited in those BFSes). The obvious solution would be to run this on every vertex of the graph, but that will end up being $O(|E||V| + |V|^{2})$. I’ve considered identifying strongly connected components, but that doesn’t seem like the right approach, since a SCC requires that $v$ and $w$ are mutually reachable, whereas this homework question requires that $v$ and $w$ are only reachable one way. Advice?
Asked By : BrokenBridges
Answered By : Yuval Filmus
We can assume that the DAG is connected, since otherwise the solution is trivial. Consider some topological ordering of the vertices. A vertex $v$ satisfies your condition if (1) $v$ can be reached from all vertices preceding $v$ in the ordering and (2) all vertices following $v$ in the ordering are reachable from $v$. We can check conditions (1) and (2) separately. To check condition (2), traverse the topological ordering in order, and for each vertex encountered, remove the vertex. Since this is a topological ordering, when a vertex is removed, it is a source, that is, it has no incoming edges. Condition (2) is satisfied for the vertex iff it is the unique source at that point. Condition (1) can be checked similarly by traversing the topological ordering in reverse.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30176
