找出知晓秘密的所有专家

标签: 深度优先搜索 广度优先搜索 并查集 图 排序

难度: Hard

给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。

专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。

秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。

在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。

示例 1：

输入：n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
输出：[0,1,2,3,5]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 5 ，专家 1 将秘密与专家 2 共享。
时间 8 ，专家 2 将秘密与专家 3 共享。
时间 10 ，专家 1 将秘密与专家 5 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 5 都将知晓这个秘密。

示例 2：

输入：n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
输出：[0,1,3]
解释：
时间 0 ，专家 0 将秘密与专家 3 共享。
时间 2 ，专家 1 与专家 2 都不知晓这个秘密。
时间 3 ，专家 3 将秘密与专家 0 和专家 1 共享。
因此，在所有会议结束后，专家 0、1 和 3 都将知晓这个秘密。

示例 3：

输入：n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
输出：[0,1,2,3,4]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 1 ，专家 1 将秘密与专家 2 共享，专家 2 将秘密与专家 3 共享。
注意，专家 2 可以在收到秘密的同一时间分享此秘密。
时间 2 ，专家 3 将秘密与专家 4 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 4 都将知晓这个秘密。

提示：

  • 2 <= n <= 105
  • 1 <= meetings.length <= 105
  • meetings[i].length == 3
  • 0 <= xi, yi <= n - 1
  • xi != yi
  • 1 <= timei <= 105
  • 1 <= firstPerson <= n - 1

Submission

运行时间: 229 ms

内存: 63.6 MB

class Solution:
    def findAllPeople(self, n: int, A: List[List[int]], fp: int) -> List[int]:
        inf = 0xffffff
        G = [[] for _ in range(n)]
        for x,y,t in A:
            G[x].append((t,y))
            G[y].append((t,x))
        q = {0, fp}
        dis = [inf]*n; dis[0] = 0; dis[fp] = 0
        while q:
            u = q.pop()
            for tv,v in G[u]:
                if tv >= dis[u] and dis[v] > tv:
                    dis[v] = tv                    
                    q.add(v)
        return [i for i in range(n) if inf!=dis[i]]

Explain

此题解利用了图的广度优先搜索（BFS）的变体来传递信息。首先，创建一个图G，其中每个节点表示一个专家，边则代表两个专家在特定时间的会面。图中每个节点连接到的边带有时间标签，这样可以确保只有在正确的时间，专家才能互相分享秘密。初始化一个队列q，其中包含初始知道秘密的专家0和firstPerson。使用一个数组dis来记录每个专家最早知道秘密的时间。在遍历的过程中，如果当前专家在会议时间之前已经知道秘密，并且这个会议时间早于或等于目标专家的已知时间，则更新目标专家的已知时间并将其加入队列。最终，遍历dis数组，将所有不是无穷大的索引（代表这些专家知道了秘密）收集起来返回。

时间复杂度: O(m)

空间复杂度: O(m + n)

# 定义解决方案类
class Solution:
    def findAllPeople(self, n: int, A: List[List[int]], fp: int) -> List[int]:
        inf = 0xffffff  # 定义无穷大，用于初始化未知的最小时间
        G = [[] for _ in range(n)]  # 创建每个专家的会议列表
        for x, y, t in A:  # 遍历所有会议，构建图
            G[x].append((t, y))
            G[y].append((t, x))
        q = {0, fp}  # 初始化队列，包含最初知道秘密的专家0和firstPerson
        dis = [inf] * n; dis[0] = 0; dis[fp] = 0  # 初始化每个专家知道秘密的最早时间
        while q:  # BFS循环
            u = q.pop()  # 取出一个专家
            for tv, v in G[u]:  # 检查所有与此专家的会议
                if tv >= dis[u] and dis[v] > tv:  # 如果会议时间合适，并且可以更新目标专家的时间
                    dis[v] = tv  # 更新时间
                    q.add(v)  # 将更新后的专家加入队列
        return [i for i in range(n) if inf != dis[i]]  # 返回知道秘密的所有专家的列表

Explore

在构建图G时选择使用列表的列表（即邻接表）主要基于存储效率和访问速度的考虑。对于稀疏图，即边的数目远小于顶点数的平方，邻接表比邻接矩阵更节省空间，因为它只需要存储存在的边。此外，使用邻接表可以更快地遍历一个顶点的所有邻接点，这在BFS中非常有用，因为我们通常需要快速访问一个顶点的所有邻接顶点。而使用哈希表虽然也可以实现类似的结构，但在这种情况下增加了不必要的复杂度和可能的性能开销，因为列表已经足够满足需求。

在题解中使用无穷大的值（如0xffffff）来初始化dis数组是为了标记那些还未知晓秘密的专家。这种方法并非在所有编程语言中都是通用的，不同的编程语言和环境可能需要不同的方式来表示足够大的数值。在一些语言中，可能直接有表示无穷大的内置值（如Python中的float('inf')），而在其他如C或Java中，可能需要使用最大整数值MAX_INT来近似。在实现时，应选择该语言中表示极大数值的标准方式，或者根据问题的具体需求选择一个足够大的数值，以确保它不会被任何有效的时间戳覆盖。