Loud and Rich Python Solution with Tests

lcpy gen -n 851   # by problem number
lcpy gen -s loud_and_rich   # by problem name

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation:
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.

Input: richer = [], quiet = [0]
Output: [0]

class Solution:
    # Time: O(n + e)
    # Space: O(n + e)
    def loud_and_rich(self, richer: list[list[int]], quiet: list[int]) -> list[int]:
        n = len(quiet)
        graph: list[list[int]] = [[] for _ in range(n)]
        for a, b in richer:
            graph[b].append(a)

        answer: list[int] = [-1] * n

        def dfs(x: int) -> int:
            if answer[x] != -1:
                return answer[x]
            best = x
            for y in graph[x]:
                cand = dfs(y)
                if quiet[cand] < quiet[best]:
                    best = cand
            answer[x] = best
            return best

        return [dfs(i) for i in range(n)]