Hi Abhi,
I think there is still some confusion regarding the celebrity problem. Let me explain once again. There are two versions. In the first, everyone knows the celebrity but celebrity doesn't know any one. The solution to this is quite easy. In the version I asked, everyone knows the celebrity and a person may randomly know any number of other persons one of whom is certainly a celebrity. Celebrity might also know several people. One condition is that there's only one celebrity. So for a person P, let the indegree be the number of people who know P and outdegree be the number of people P knows. For celebrity, indegree is 'N', outdegree can be anything. Such a person with indegree of N is unique in this problem. Can you find such a person. For example, Let there be 4 persons A,B,C,D. A knows B,D --> knows(A,B) and knows(A,D) return true and knows(A,C) returns fase B knows D --> knows(B,A), knows(B,C) return false and knows(B,D) returns true C knows A,D --> knows(C,A), knows(C,D) return true and knows(C,B) returns false D knows A,B,C --> knows(D,A), knows(D,B), knows(D,C) return true. Here in this case, D is the celebrity. Any comments on the solution I presented ? This also gives me idea of another version, what if there are several celebrities and we need to find all of them? But first let there be no confusion regarding the problem.
