Topological sort:

When an adjacency matrix representation is used, most graph algorithms require time O(n^2) (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 n n adjacency matrix.