Social engineering. $(20$ points$)$

Suppose we have a community of $n$ people. We can create a directed graph from this

community as follows: the vertices are people, and there is a directed edge from person

$A$ to person $B$ if A would forward a rumor to $B.$ Assume that if there is an edge from $A$

to $B,$ then A will always forward any rumor they hear to $B.$ Notice that this relationship

isn't symmetric: A might gossip to $B$ but not vice versa. Suppose there are $m$ directed

edges total, so $G=(V,E)$ is a graph with $n$ vertices and $m$ edges.

Define a person $P$ to be influential if for all other people $A$ in the community, there is

a directed path from $P$ to $A$ in $G.$ Thus, if you tell a rumor to an influential person $P,$

eventually the rumor will reach everybody. You have a rumor that you'd like to spread,

but you don't have time to tell more than one person, so you'd like to find an influential

person to tell the rumor to$.$

In the following questions, assume that $G$ is the directed graph representing the commu$-$

nity, and that you have access to $G$ as an array of adjacency lists: for each vertex $v,$ in

$O(1)$ time you can get a pointer to the head of the linked lists $v.$outgoing$\_$neighbors

and $v.$incoming$\_$neighbors. Notice that $G$ is not necessarily acyclic. In your answers,

you may appeal to any statements we have seen in class, in the notes, or in CLRS$.$

$($a$)(10$ points$)$ Show that all influential people in $G$ are in the same strongly connected

component, and that everyone in this strongly connected component is influential.

$[$Hint: You need to refer the definition of strongly connected component,

and you can prove using either induction or contradiction.$]$

$($b$)(10$ points$)$ Suppose that an influential person exists. Give an algorithm that, given

$G,$ finds an influential person.

$[$We are expecting a description or pseudocode of your algorithm and a

short argument about the runtime. You can borrow any algorithm that

we have learned in class.$]$