Geek Answers Handbook

Linear celebrity group search algorithm, not the only celebrity

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

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

If you are given a function know x ythat returns true or false, define a group of celebrities.

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

Using brute force is easy. I can build all possible subsequences of N people and filter them with a condition (everyone knows that every celebrity and every celebrity knows only another celebrity).

I also know that there should be only one group of celebrities or not.

Evidence:

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; Thus, C1 and C2 actually belong to the same group. Thus, we have no more than one group of celebrities or not.

Any ideas on a possible linear algorithm ?

change

There may be a group of celebrities, and they may not be.

+4
source share
5 answers

, O (N) ( . ). .

N 0 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();

C==-1, . { y | know(C,y) } . , 3 N , 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;

2:

:

  • , . , .
  • , , .

№1. №2, , . , , O(N*M) , M - .

+8

EDIT: . , , .

, . V () E (), .

E, , . V-1 ; . O (E).

0

- , . - , . :

foreach person in persons
{
  knows = know(person, next_person)
  isknown = know(next_person, person)

  if knows and !isknown then normal
  if !knows and isknown then celeb
  if !knows and !isknown then normal
  if knows and isknown then friends.add(person)

  foreach friend in friends
  {
      alsoknows = know(person, friend)
      if !alsoknows then normal; break;
  }
}
0

, N * (N-1) (x, y) . N - . , , N * (N-1), (x, y). , , . , N * (N-1).

0

candidates n . :

1 -> 2 -> ... -> n -> 1.

, knows k,k+1. true, k = k+1, . knows k,k+1 == False, , k+1 , candidates k,k+2.

, size(candidates) .

:

, :

  • , .
  • " ", , 2.

, .

If there are no celebrities on the list, follow @Matt's answers.

-1
source

More articles:


All Articles