851.喧闹和富有

原题

就是拓扑排序，利用richer的传递性（a->b,b->c,则a->c)，每次更新一个节点的ans并传递下去。

class Solution:
    def loudAndRich(self, richer, quiet) :
        g, n = defaultdict(list), len(quiet)
        inDegree = [0] * n    #入度
        for u, v in richer:     #建立邻接表
            g[u].append(v)
            inDegree[v] += 1
        #入度为0的节点入队
        q = queue.Queue()
        for u in range(n):
            if not inDegree[u]:
                q.put(u)
        #初始ans[i] = i
        ans = list(range(n))
        # 拓扑排序，每次出队一个入度为0的节点
        while not q.empty():
            u = q.get()
            for v in g[u]:	#遍历u的邻节点
                #比较安静值（注意不是u和v，而是前面传递来的，即ans[u] ans[v]）
                if quiet[ans[u]] < quiet[ans[v]]:
                    ans[v] = ans[u]
                inDegree[v] -= 1
                if not inDegree[v]:
                    q.put(v)
        return ans