algorithm - 寻找名人群体的线性算法，而不是单个名人

Question

假设我们有 N 个人，里面可能一群名人。

每个人都认识每个名人，每个名人只认识其他每个名人。

如果给你know x y函数，返回 true 或 false，请识别名人组。

本题是识别出一群名人，而不是识别出人群中唯一的名人，比如http://www.geeksforgeeks.org/the-celebrity-problem/ .

---

使用蛮力很容易。我可以构建 N 个人所有可能的子序列，并用条件过滤它们(每个人都认识每个名人，每个名人只认识其他名人)。

我也知道一定只有一个名人团体，或者没有。

证明:

假设我们有两个名人群体，C1 和 C2。因为每个人都知道 C1 中的 ci，所以 C2 中的每个 cj 也都知道 ci；对称地，每个 ci 都知道 cj；所以C1和C2其实属于一个组。所以我们最多有一个名人团体，或者没有。

对可能的线性算法有什么想法吗？

编辑

可能有一群名人，也可能没有。

Answer 1

是的，这在 O(N) 中是可能的(但请参阅下面的第二次编辑)。这是一种算法。

从0到N-1枚举所有N个人。

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) } 是所有名人的集合。总之，这对所有 N 个人最多进行了 3 次迭代，因此及时发现了 O(N)。

编辑:

// 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. 名人的定义是人尽皆知，名人只认识其他名人。

上述算法针对案例 #1 解决了这个问题。这也适用于案例 #2，只要我们可以假设至少存在一位名人。否则，我们将不得不在最后验证潜在名人列表中是否只相互认识，这需要 O(N*M) 时间，其中 M 是潜在名人的数量。