解释

为了方便，我们令点数为n ，边数为m 。

在图论中，一个有向无环图必然存在至少一个拓扑序与之对应，反之亦然。

拓扑排序：简单来说，就是将图中的所有节点展开成一维序列，对于序列中任意的节点 ，如果在序列中 在 的前面，则说明在图中存在从 出发达到 的通路，即 排在 的前面。反之亦然。

同时，我们需要知晓「入度」和「出度」的概念：

• 入度：有多少条边直接指向该节点；
• 出度：由该节点指出边的有多少条。

因此，对于有向图的拓扑排序，我们可以使用如下思路输出拓扑序（BFS 方式）：

1.起始时，将所有入度为 0 的节点进行入队（入度为 0，说明没有边指向这些节点，将它们放到拓扑排序的首部，不会违反拓扑序定义）；

2.从队列中进行节点出队操作，出队序列就是对应我们输出的拓扑序。对于当前弹出的节点 x，遍历x 的所有出度y，即遍历所有由 x直接指向的节点y，对y做入度减一操作（因为x节点已经从队列中弹出，被添加到拓扑序中，等价于x节点从有向图中被移除，相应的由x发出的边也应当被删除，带来的影响是与 x相连的节点y的入度减一）；

3.对y进行入度减一之后，检查 y的入度是否为0，如果为0则将y入队（当y的入度为0，说明有向图中在y前面的所有的节点均被添加到拓扑序中，此时 可以作为拓扑序的某个片段的首部被添加，而不是违反拓扑序的定义）；

4.循环流程 2、3 直到队列为空。

证明

上述 BFS 方法能够求得「某个有向无环图的拓扑序」的前提是：我们必然能够找到（至少）一个「入度为0 的点」，在起始时将其入队。

这可以使用反证法进行证明：假设有向无环图的拓扑序不存在入度为0的点。

那么从图中的任意节点 x进行出发，沿着边进行反向检索，由于不存在入度为 0 的节点，因此每个点都能够找到上一个节点。

当我们找到一条长度为n+1的反向路径时，由于我们图中只有n个节点，因此必然有至少一个节点在该路径中重复出现，即该反向路径中存在环，与我们「有向无环图」的起始条件冲突。

得证「有向无环图的拓扑序」必然存在（至少）一个「入度为0的点」。

即按照上述的 BFS 方法，我们能够按照流程迭代下去，直到将有向无环图的所有节点从队列中弹出。

反之，如果一个图不是「有向无环图」的话，我们是无法将所有节点入队的，因此能够通过入队节点数量是否为 来判断是否为有向无环图。

例题

• 喧闹和富有

题目描述

有一组 n 个人作为实验对象，从 0 到 n - 1

编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person

x "。

给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi

更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据逻辑自洽（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x更有钱的情况 ）。

现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。

示例

示例 1：

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

输出：[5,5,2,5,4,5,6,7]

解释： answer[0] = 5， person 5 比person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7， 但是目前还不清楚他是否比 person 0 更有钱。answer[7] = 7， 在所有拥有的钱肯定不少于 person 7 的人中（这可能包括 person 3，4，5，6 以及 7），最安静（有较低安静值 quiet[x]）的人是 person 7。 其他的答案也可以用类似的推理来解释。

示例 2：

输入：richer = [], quiet = [0] 输出：[0]

拓扑排序解法

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        g = [[] for _ in range(n)]
        inDeg = [0] * n
        for r in richer:
            g[r[0]].append(r[1])
            inDeg[r[1]] += 1
        ans = list(range(n))
        q = deque(i for i, deg in enumerate(inDeg) if deg == 0)
        while q:
            x = q.popleft()
            for y in g[x]:
                if quiet[ans[x]] < quiet[ans[y]]:
                    ans[y] = ans[x]  # 更新 x 的邻居的答案
                inDeg[y] -= 1
                if inDeg[y] == 0:
                    q.append(y)
        return ans