2022.3.30 图论——名流问题

文章目录

• 一、今日刷题
• • 1.题目
  • 2.分析
  • 3.代码
  • • ①暴力破解
    • ②链表存储法
    • ③无需链表的复杂度最佳解法

一、今日刷题

1.题目

277. 搜索名人

假设你是一个专业的狗仔，参加了一个 n 人派对，其中每个人被从 0 到 n – 1 标号。
在这个派对人群当中可能存在一位 “名人”。
所谓 “名人” 的定义是：其他所有 n – 1 个人都认识他/她，而他/她并不认识其他任何人。

现在你想要确认这个 “名人” 是谁，或者确定这里没有 “名人”。
而你唯一能做的就是问诸如 “A 你好呀，请问你认不认识 B呀？” 的问题，以确定 A 是否认识 B。
你需要在（渐近意义上）尽可能少的问题内来确定这位 “名人” 是谁（或者确定这里没有 “名人”）。

在本题中，你可以使用辅助函数 bool knows(a, b) 获取到 A 是否认识 B。请你来实现一个函数 int findCelebrity(n)。

派对最多只会有一个 “名人” 参加。
若 “名人” 存在，请返回他/她的编号；若 “名人” 不存在，请返回 -1。

2.分析

参考文章

给你 n 个人的社交关系（你知道任意两个人之间是否认识），然后请你找出这些人中的「名人」。
所谓「名人」有两个条件：

1、所有其他人都认识「名人」。
2、「名人」不认识任何其他人。

如果把每个人看做图中的节点，「认识」这种关系看做是节点之间的有向边，那么名人就是这幅图中一个特殊的节点：
没有一条指向其他节点的有向边；且其他所有节点都有一条指向这个节点的有向边。
即，名人节点的出度为 0，入度为 n – 1。

3.代码

函数签名：

// 可以直接调用，能够返回 i 是否认识 j
boolean knows(int i, int j);

// 请你实现：返回「名人」的编号
int findCelebrity(int n) {
   
    // todo
}

①暴力破解

两层 for 循环，对所有节点逐个判断其是否满足 “名人” 的条件。

int findCelebrity(int n) {
   
    for (int cand = 0; cand < n; cand++) {