Linear algorithm for finding the celebrity group, not single celebrity

Question

Suppose we have N people and there might be a group of celebrities inside.

Every person knows every celebrity and every celebrity knows only every other celebrity.

If you are given the function of know x y which returns true or false, identify the group of celebrities.

This problem is to identify a group of celebrities, and it is not identifying the only celebrity among the people, such as http://www.geeksforgeeks.org/the-celebrity-problem/.

---

Using brute force is easy. I can construct all possible sub-sequences of N people and filter them with the condition (everyone knows every celebrity and every celebrity knows only other celebrity).

Also I know there must be only one celebrity group or none.

Proof:

Suppose we have two celebrity groups, C1 and C2. Because everyone knows ci from C1, so every cj from C2 also knows ci; symmetrically, every ci knows cj; So C1 and C2 actually belongs to one group. So we have at most one celebrity group or none.

Any ideas on possible linear algorithm?

edit

There might be a group of celebrity and there might be none.

Answer 1

Yes, this is possible in O(N) (but see 2nd edit below). Here's one algorithm.

Enumerate all N people from 0 to N-1.

int find_a_celebrity()
{
    int C = 0; // C is a potential celebrity
    for( int i=0 ; i<N ; ++i )
      if( !know(i,C) ) // C is not a celebrity nor are all j<i, but i might be.
        C = i; 
    for( int i=0 ; i<N ; ++i ) // Loop a second time to check everyone knows C.
      if( !know(i,C) ) return -1;
    return C;
}
int C = find_a_celebrity();

If C==-1 then there are no celebrities. Otherwise the set { y | know(C,y) } is the set of all celebrities. All together, this took at most 3 iterations through all N people, so this is discovered in time O(N).

Edit:

// Output the set of celebrities
if( C == -1 ) std::cout << "There are no celebrities.";
else for( int i=0 ; i<N ; ++i ) if( know(C,i) ) std::cout << i << ' ';
std::cout << std::endl;

Edit 2:

There are two interpretations to this problem:

1. The definition of a celebrity is that they are known by everyone. By a constraint of the problem, all celebrities only know other celebrities.
2. The definition of a celebrity is that they are known by everyone, and celebrities only know other celebrities.

The above algorithm solves this for case #1. This works for case #2 as well, as long as we can assume that there exists at least one celebrity. Otherwise we will have to verify at the end that the list of potential celebrities only know each other, which requires O(N*M) time where M is the number of potential celebrities.