Leetcode: 2092. Find All People With Secret

Mistake: Incorrect evaluation of solution's viability. I computed the connections to person 0, by looking to the edges that starts on person 0 component. The problem is that it will become \(O(n^2)\) in the worst case and not \(O(m)\).
Pattern: Build graph online. For each meeting time, we add all edges using Union-Find from the meetings to the graph and after that we remove all those edges which its vertices aren't connected to the vertex 0.
How can we extend the solution for \(i\) to \(i+1\)? We are going to build the solution by time. Group all meetings by their times. From the earlier to the later meeting, connect the vertices (people) that met at that time. On the end, reset the connected components other the one that has people 0 on it. Time complexity is \(O(m)\) and space is \(O(n)\).

from typing import List


class Solution:
    def findAllPeople(
        self, n: int, meetings: List[List[int]], firstPerson: int
    ) -> List[int]:
        p = [i for i in range(n)]

        def find(u):
            if p[u] != u:
                p[u] = find(p[u])
            return p[u]

        def union(u, v):
            p[find(u)] = p[find(v)]

        union(0, firstPerson)

        m = {t: [] for _, _, t in meetings}
        for u, v, t in meetings:
            m[t].append((u, v))

        for t in sorted(m):
            vs = set()
            for u, v in m[t]:
                union(u, v)
                vs.add(u)
                vs.add(v)
            for u in vs:
                if find(u) != find(0):
                    p[u] = u

        return [u for u in range(n) if find(u) == find(0)]


assert Solution().findAllPeople(6, [[1, 2, 5], [2, 3, 8], [1, 5, 10]], 1) == [
    0,
    1,
    2,
    3,
    5,
]
assert Solution().findAllPeople(4, [[3, 1, 3], [1, 2, 2], [0, 3, 3]], 3) == [0, 1, 3]
assert Solution().findAllPeople(5, [[3, 4, 2], [1, 2, 1], [2, 3, 1]], 1) == [
    0,
    1,
    2,
    3,
    4,
]