Gossip Mongering. We represent a group of n people as a directed graph G = (V, E) where an edge (u, v) means that u will tell a "secret" to v. Since it might be the case that u tells secrets to v but v will not tell secrets to u, there may or may not be an edge (v, u) in the other direction.

Suppose that you wanted to start some sort of rumor, something like "They are giving away free pizza on third floor of ITE." You want everyone to find out, but to reduce the chance of getting caught spreading baseless rumors, you want to tell as few people as possible yourself. Thus, you want to identify a subset C of the vertices such that for every vertex v in G there is a directed path from some vertex u C to v. Your assumption is that if you tell every u C about the free pizza, then every v V will eventually hear the rumor (possibly through intermediaries). Note that if C is as small as possible, then there cannot be paths between two vertices in C. (You didn't have to tell the rumor to one of them and everyone would still find out.)

A) Devise an algorithm to find the smallest set C with the properties described above. Describe your algorithm at a high level (try to avoid pseudocode). For full credit your algorithm should run in O(V + E) time.

B) Argue that your algorithm is correct. That is, argue that for every v V, there exists u C such that there is a directed path from u to v in G. Then, argue that the C produced by your algorithm is the smallest possible.

C) State and briefly justify the running time of your algorithm.

Hint: First, devise an algorithm for acyclic graphs. Then, generalize your algorithm to work with graphs that may contain cycles.

Note: the graph does not include yourself. In particular, you do have the option of spreading the rumor by personally telling every vertex in the graph. However, the only case where this is the smallest set of people to tell is when the graph has no edges at all.