Ohh... IC Now I understood your other version of the problem. Here the simplest program we can write would be to call the function (P,Q) for all P,Q from 1 to N, and then count the indegree, as you have rightly told. This would have time-complexity of N*N.
To improve the time. We can apply some of the graph theory algorithms. I guess minimum spanning tree would be quite a good candidate for this problem. Here we can treat each person as a node, person P knowing Q would be a directed edge of unit weight. The final minimum tree would have just the edges where every node is pointing to the celebrity. This site explains the algorithm http://www.ce.rit.edu/~sjyeec/dmst.html Regards, -Abhi
