2092. 找出所有拥有秘密的人

Source: Dev.to

Problem Description

给定一个整数 n，表示有 n 个人，编号从 0 到 n - 1。
还给定一个 0 索引的二维整数数组 meetings，其中 meetings[i] = [xᵢ, yᵢ, timeᵢ] 表示人物 xᵢ 与人物 yᵢ 在 timeᵢ 时刻进行一次会面。一个人在同一时间可以参加多次会面。

最后，给定一个整数 firstPerson。

人物 0 拥有一个秘密，并在时间 0 时立即将该秘密分享给 firstPerson。此后，每当有会议发生且与会者中有人拥有该秘密时，秘密会在与会者之间传播。更形式化地说，对于每一次会议，如果人物 xᵢ 在 timeᵢ 时刻拥有秘密，则他们会把秘密分享给人物 yᵢ，反之亦然。

秘密的传播是瞬时的。也就是说，一个人可以在同一时间框内收到秘密后，再立即在其他会议中把秘密传出去。

返回所有在所有会议结束后拥有该秘密的人的列表。答案的顺序可以任意。

Examples

Example 1

Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Output: [0,1,2,3,5]

Explanation:

• 在时间 0，人物 0 把秘密分享给人物 1。
• 在时间 5，人物 1 把秘密分享给人物 2。
• 在时间 8，人物 2 把秘密分享给人物 3。
• 在时间 10，人物 1 把秘密分享给人物 5。

因此，人物 0、 1、 2、 3 和 5 在所有会议结束后都知道该秘密。

Example 2

Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]

Explanation:

• 在时间 0，人物 0 把秘密分享给人物 3。
• 在时间 2，人物 1 和人物 2 都不知道秘密。
• 在时间 3，人物 3 把秘密分别分享给人物 0 和人物 1。

因此，人物 0、 1 和 3 在所有会议结束后都知道该秘密。

Example 3

Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output: [0,1,2,3,4]

Explanation:

• 在时间 0，人物 0 把秘密分享给人物 1。
• 在时间 1，人物 1 把秘密分享给人物 2，人物 2 又把秘密分享给人物 3（秘密可以在同一时间框内传递）。
• 在时间 2，人物 3 把秘密分享给人物 4。

因此，人物 0、 1、 2、 3、 4 在所有会议结束后都知道该秘密。

Constraints

• `2 $a[2] $b[2]);

  // Union‑Find data structures. $parent = range(0, $n - 1); $size = array_fill(0, $n, 1);

  // Helper functions. $find = function (int $x) use (&$parent, &$find): int { if ($parent[$x] !== $x) { $parent[$x] = $find($parent[$x]); // Path compression. } return $parent[$x]; };

  $union = function (int $a, int $b) use (&$parent, &$size, $find): void { $ra = $find($a); $rb = $find($b); if ($ra === $rb) return; // Union by size. if ($size[$ra]

## Complexity Analysis  

- **Time Complexity:**  
  对会议进行排序的时间复杂度为 `O(m log m)`，其中 `m = meetings.length`。  
  处理每一次会议涉及近乎常数时间的并查集操作，总体为 `O(m α(n))`，其中 `α` 为反阿克曼函数（在实际中可以视为常数）。  

- **Space Complexity:**  
  `O(n + m)` 用于存放并查集数组以及分组后的会议信息。