Finding the celebrity group

Problem

Given the group of people in party find the group of celebrities

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 Knows(x,y) which returns true if x knows y, false otherwise. 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://k2code.blogspot.in/2014/04/the-celebrity-problem.html.

Solution
Method 1 - Brute force
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.

Method 2 - Linear solution

int find_a_celebrity()
{
    int C = 0; // C is a potential celebrity
    for( int i=0 ; i<N ; ++i )
      if( !knows(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( !knows(i,C) ) return -1;
    return C;
}

int C = find_a_celebrity();

If C==-1 then there are no celebrities. Otherwise the set { y | knows(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).

References
http://stackoverflow.com/questions/20983260/linear-algorithm-for-finding-the-celebrity-group-not-single-celebrity