leetcode 851 喧闹和富有 Loud and Rich - python

目录

1. 解题思路
2. 代码

https://leetcode-cn.com/problems/loud-and-rich/

解题思路

根据第一个例子：

richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]

首先构造这个图，我们同时要保存最上面的人，也就是最富的人，把 ans 初始化每个人自己。

然后我们通过广度优先遍历，一层一层的往下，更新 ans

代码

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        poorer = [[] for i in range(n)]
        toper = set()
        for x, y in richer:
            poorer[x].append(y)
            if y in toper: toper.remove(y)
            toper.add(x)
        ans = [i for i in range(n)]
        while toper:
            new_set = set()
            for rich in toper:
                for poor in poorer[rich]:
                    if quiet[ans[poor]] > quiet[ans[rich]]:
                        ans[poor] = ans[rich]
                    new_set.add(poor)
            toper = new_set
        return ans