Mayor Problem; universal sink

Ina city mayor elections wer der.....so ppl decided to choose such a person so that all ppl know him but that person does not know anyone....write an algo to find that person

construct a graph node which is pointed by every node and no node is pointed by it

am i right?????

Ya u r right....got the logic...same as universal sink....

Ya it's the same universal sink problem ... in maximum of 2n traversal in the array representation of list u can find the solution.

answer is o(n) but not in 2n

also there are two cases
1) represent graph as array
2) graph is represented as linklist

I wrote maximum of 2n, which automatically means O(n).