Find All People With Secret Python Solution

lcpy gen -n 2092   # by problem number
lcpy gen -s find_all_people_with_secret   # by problem name

Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Output: [0,1,2,3,5]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 5, person 1 shares the secret with person 2.
At time 8, person 2 shares the secret with person 3.
At time 10, person 1 shares the secret with person 5.
Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]
Explanation:
At time 0, person 0 shares the secret with person 3.
At time 2, neither person 1 nor person 2 know the secret.
At time 3, person 3 shares the secret with person 0 and person 1.
Thus, people 0, 1, and 3 know the secret after all the meetings.

Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output: [0,1,2,3,4]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3.
Note that person 2 can share the secret at the same time as receiving it.
At time 2, person 3 shares the secret with person 4.
Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

class Solution:
    # Time: O(m log m) for sorting meetings plus near-linear union-find passes
    # Space: O(n) for the parent array
    def find_all_people(self, n: int, meetings: list[list[int]], first_person: int) -> list[int]:
        parent = list(range(n))

        def find(node: int) -> int:
            while parent[node] != node:
                parent[node] = parent[parent[node]]
                node = parent[node]
            return node

        def union(a: int, b: int) -> None:
            root_a, root_b = find(a), find(b)
            if root_a != root_b:
                parent[root_a] = root_b

        known = {0, first_person}
        sorted_meetings = sorted(meetings, key=lambda meeting: meeting[2])
        i = 0
        total = len(sorted_meetings)
        while i < total:
            time = sorted_meetings[i][2]
            participants: set[int] = set()
            while i < total and sorted_meetings[i][2] == time:
                x, y, _ = sorted_meetings[i]
                union(x, y)
                participants.update((x, y))
                i += 1
            knower_roots = {find(p) for p in participants if p in known}
            for person in participants:
                if find(person) in knower_roots:
                    known.add(person)
            for person in participants:
                parent[person] = person
        return list(known)