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

Reply via email to