2
$\begingroup$

In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover problem nor dominating-set problem since we don't need to select node 3. We say that, if we select node 0, we can go to node 1 from there and if we select node 2, we can go to node 3 and then node 4 from there.

Also, the number of nodes can be up to 10^5 and the algorithm's runtime must be 1 second or less. Any suggestion would be useful.

graph

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Try combining Tarjan's strongly connected components algorithm with a topological sort.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I have implemented a SCC algorithm and now I have number of components and know which node in which component. Now I need to create a new graph I think, to apply topological sort on it. Right? However, I can't figure out how to create the new graph? A little bit help please? $\endgroup$
    – WhoCares
    Nov 14, 2018 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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