题目描述

在一组 N 个人（编号为 0, 1, 2, ..., N-1）中，每个人都有不同数目的钱，以及不同程度的安静（quietness）。

为了方便起见，我们将编号为 x 的人简称为 “x“。

如果能够肯定 x 比 y 更有钱的话，我们会说 richer[i] = [x, y]。注意 richer 可能只是有效观察的一个子集。

另外，如果 x 的安静程度为 q，我们会说 quiet[x] = q。

现在，返回答案 answer，其中 answer[x] = y 的前提是，在所有拥有的钱不少于 x 的人中，y 是最安静的人（也就是安静值 quiet[y] 最小的人）。

样例

输入：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。

其他的答案也可以用类似的推理来解释。

注意

• 1 <= quiet.length = N <= 500
• 0 <= quiet[i] < N，所有 quiet[i] 都不相同。
• 0 <= richer.length <= N * (N-1) / 2
• 0 <= richer[i][j] < N
• richer[i][0] != richer[i][1]
• richer[i] 都是不同的。
• 对 richer 的观察在逻辑上是一致的。

算法

(拓扑排序) $O(m + n)$

1. 将 richer 中描述的关系看做边，如果 x > y，则 x 向 y 连边。将 quiet 看做一个权值。
2. 开一个数组记录答案，初始时 ans[i] = i。然后对原图做拓扑排序，对于每一条边，如果发现 quiet[ans[v]] > quiet[ans[u]]，则 ans[v] 的答案为 ans[u]。

时间复杂度

• 拓扑排序的时间复杂度为 $O(m + n)$。

空间复杂度

• 需要 $O(m)$ 的数组建图，需要 $O(n)$ 的数组记录入度以及存储队列，故空间复杂度为 $O(m + n)$。

C++ 代码

class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        int n = quiet.size();
        vector<vector<int>> edges(n);
        vector<int> deg(n, 0);

        for (auto &e : richer) {
            edges[e[0]].push_back(e[1]);
            deg[e[1]]++;
        }

        queue<int> q;
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = i;
            if (deg[i] == 0)
                q.push(i);
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &v : edges[u]) {
                deg[v]--;
                if (quiet[ans[v]] > quiet[ans[u]])
                    ans[v] = ans[u];
                if (deg[v] == 0)
                    q.push(v);
            }
        }
        return ans;
    }
};