When an adjacency matrix representation is used, most graph algorithms require time O(n²)

(where n is the number of vertices), but there are some exceptions. Heres one.

Kumiko and her bandmates are having a election to determine the next school band president,

and every band member is competing for it. Each candidate has a few preferences (people who

the person would be willing to accept as as band president). Of course, the set of preferences

for a person includes him/her self all the time.

What we are looking for is a perfect president who is in the set of preferences of every person

and who does not prefer anyone but him/her self (wouldnt that make a good president?). In

fact, all we want to know whether such a person exists or not. Otherwise, were willing to live

in anarchy. Define a directed graph with the set of candidates as the vertices and a directed

edge from vertex a to vertex b if and only if b is in the set of preferences of a.

Suppose that the number of people (also the number of candidates) is n. Give an algorithm

which executes in O(n) time and determines if such a perfect presidential candidate exists or

not. Assume that you are given the graph described above in the form of an nn adjacency matrix.