# Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached

Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached.

I thought to run an SCC algorithm to find binding components and then return them. This is true? Or is there a better algorithm?

• What are the strongly connected components of a graph without circles? Are you familiar with the concepts of sources and sinks? – Pål GD Jan 21 at 11:03
• Try using a topological sort. – Yuval Filmus Jan 21 at 11:17
• After the use of topological sort, there is a row of vertices arranged by a forward edge, what is the next step? – Kate Jan 21 at 13:35

Considering the strongly connected component is a good start if graph $$G$$ may have cycles. However, as implied by Pål GD, every vertex is a strongly connected component of a graph without cycles. We need to do more work to find the minimum set of vertices from which all vertices can be reached.
1. Find one root $$r$$ of $$G$$ by repeatedly going to the ancestor of a node. Mark $$r$$ as an wanted vertex.
2. Remove all vertices reachable from $$r$$.