크고 풍부한

n에서 0까지 레이블이 지정된 n - 1명의 그룹이 있으며 각 사람은 다른 금액과 다른 수준의 조용함을 가지고 있습니다.
richer가 richer[i] = [ai, bi]가 ai보다 더 많은 돈을 가지고 있음을 나타내는 배열 bi와 quiet가 quiet[i] 사람의 조용함인 정수 배열 ith가 제공됩니다. richer의 모든 주어진 데이터는 논리적으로 정확합니다(즉, 데이터는 x가 y보다 풍부하고 y가 x보다 동시에 풍부한 상황으로 이어지지 않습니다.

정수 배열answer을 반환합니다. 여기서 answer[x] = y가 가장 적게 조용한 사람(즉, y의 값이 가장 작은 사람y인 경우) 그 사람 quiet[y] .

예 1:

입력: 부자 = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], 조용함 = [3,2,5,4,6,1,7,0]
출력: [5,5,2,5,4,5,6,7]
설명:
답변[0] = 5.
사람 5는 3보다 돈이 많고, 사람 1보다 돈이 많고, 0보다 돈이 많습니다.
더 조용한(quiet[x]가 더 낮은) 유일한 사람은 사람 7이지만 사람 0보다 돈이 더 많은지는 확실하지 않습니다.
답변[7] = 7.
사람 7(사람 3, 4, 5, 6 또는 7이 될 수 있음)보다 확실히 같거나 더 많은 돈을 가진 모든 사람 중에서 가장 조용한 사람(조용함[x]이 더 낮음)은 사람 7입니다.
다른 답변도 비슷한 추론으로 채울 수 있습니다.

예 2:

입력: 풍부함 = [], 조용함 = [0]
출력: [0]

제약:

x

n == quiet.length

1 <= n <= 500

0 <= quiet[i] < n의 모든 값은 고유합니다.

quiet

0 <= richer.length <= n * (n - 1) / 2

0 <= ai, bi < n

ai != bi의 모든 쌍은 고유합니다.

richer의 관측치는 모두 논리적으로 일치합니다.

해결책:

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        graph = {}
        for a, b in richer:
            graph[b] = graph.get(b, []) + [a]
        answer = [0] * n
        for beg in range(n):
            paths = [beg]
            visited = {beg}
            while len(paths) > 0:
                curr = paths.pop()
                for j in graph.get(curr, []):
                    if j not in visited:
                        visited.add(j)
                        paths.append(j)
            answer[beg] = min(visited, key = lambda p: quiet[p])
        return answer