2092. 비밀이 있는 모든 사람 찾기

Source: Dev.to

Problem Description

정수 n이 주어집니다. 이는 0부터 n - 1까지 번호가 매겨진 사람 n명이 존재한다는 의미입니다.
또한 0‑인덱스 2차원 정수 배열 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`입니다.  
  각 회의를 처리할 때는 거의 상수에 가까운 amortized union‑find 연산이 수행되므로 `O(m α(n))` 시간이 걸립니다. 여기서 `α`는 역아커만 함수이며 실제로는 상수에 가깝습니다.  

- **Space Complexity:**  
  union‑find 배열과 그룹화된 회의를 저장하기 위해 `O(n + m)`의 추가 공간이 필요합니다.