# Given Directed Graph G(V,E) with red/black vertices, v is good if there's a path from v to a black vertex

Given Directed Graph G(V,E) with red/black vertices, v is "good" if there's a path from v to a black vertex. in linear time.

Question: Find all the good vertices in the graph

I've come up with an algorithm which almost works.

1. Run SCC on G.
2. Sort topologically.
3. Run from the last SCC till the first SCC.
4. If we find a black node, return all the previous SCCs nodes and the current SCC's nodes (because all the nodes are reachable in the SCC).

This algorithm fails because there may be SCC's which are not connected to the SCC that we found the black node. How can I fix the algorithm to work?

• Wouldn't flood fill on the dual graph just work? Or I'm understanding the problem wrong? Jul 31, 2017 at 17:07
• Your don't state that your graph acyclic. How can you do topological sort? Jul 31, 2017 at 17:33
• @fade2black After I run SCC algorithm the graph becomes DAG as far as I remember. Jul 31, 2017 at 18:01
• Sorry, you are right. I missed that part. Jul 31, 2017 at 18:02
• Do you search for a path from the vertex $v$ to some (at least one) black vertex? Jul 31, 2017 at 18:04

Lets consider the case where you need to be $$O(V+E)$$. As someone in the comments mentioned, the way I thought about it was reversing the edges, as described below:
Now, let's say you want to stick with the SCC strategy. We first find all SCC's in $$O(V+E)$$ time. Then, for each SCC we condense it to a single node and color it black if it contained a black node and red otherwise. All edges into and out of the each SCC will now lead into and out of the new corresponding condensed node. Now we can just perform the same algorithm as above on the new graph with no SCCs! For every node, mark it as good iff its corresponding SCC was visited.