1
$\begingroup$

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?

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

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:

  1. Reverse all edges
  2. For every unvisited black vertex, perform a BFS/DFS on all unvisited nodes, marking them visited as you search.
  3. All visited nodes are good.

It is trivial to see that if and only if a node is marked visited, it can reach a black vertex in the original graph. The forward direction is simple, if a node is visited, then there is a direct path to a black vertex. The other direction is also true, if there is a path from a node to a black vertex in the original graph, that that node would clearly have been visited by one of the searches.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.