find the minimum number of vertices in a directed graph from which the other vertices are reachable [closed]

Question

In a directed graph i want to call bfs on some of the vertices so that all of the vertices will be met.

(in other words all of the other vertices are reachable from these chosen vertices.)

I want to find the minimum number of such vertices.

Actually this problem arises in social networks when we want to find the minimum number of people to which if we send a message then all of the network members will get that.(suppose that we know when someone gets the message he/she will send that to all of his/her followers.)

Can anyone help?

Answer 1

For the graph without cycle(i.e acyclic graph), it will be easy. All the nodes without incoming edges will be an optimal solution. Since all other nodes should be reachable from one of the nodes.

For the graph with cycle, find strongly connected component first, then you get a acyclic graph. The method above works again.