0851-喧闹和富有

有一组 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]

提示：

• 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 中的所有数对 互不相同
• 对 ****richer 的观察在逻辑上是一致的

方法一：深度优先搜索

我们可以根据 richer 构建一张有向图：把人看成点，如果 a_i 比 b_i 更有钱，那么就从 b_i 向 a_i 连一条有向边。由于题目保证 richer 中所给出的数据逻辑自恰，我们得到的是一张有向无环图。

因此我们从图上任意一点（设为 x）出发，沿着有向边所能访问到的点，都比 x 更有钱。

题目需要计算拥有的钱肯定不少于 x 的人中，最安静的人。我们可以分为拥有的钱肯定与 x 相等，以及拥有的钱肯定比 x 多两种情况。对于前者，根据题目所给信息，我们只知道 x 拥有的钱肯定与自己相等，无法知道是否有其他人拥有的钱肯定与 x 相等；对于后者，我们可以先计算出 x 的邻居的 answer 值，再取这些 answer 值中的最小值为结果，这是因为从 x 的邻居出发所能访问到的点，并上 x 的邻居后所得到的点集，就是从 x 出发所能访问到的点。总的来说，最安静的人要么是 x 自己，要么是 x 的邻居的 answer 中最安静的人。

计算 x 的每个邻居的 answer 值是一个递归的过程，我们可以用深度优先搜索来实现。为避免重复运算，在已经计算出 answer}[x] 的情况下可以直接返回。

[sol1-Python3]

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        g = [[] for _ in range(n)]
        for r in richer:
            g[r[1]].append(r[0])

        ans = [-1] * n
        def dfs(x: int):
            if ans[x] != -1:
                return
            ans[x] = x
            for y in g[x]:
                dfs(y)
                if quiet[ans[y]] < quiet[ans[x]]:
                    ans[x] = ans[y]
        for i in range(n):
            dfs(i)
        return ans

[sol1-C++]

class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>> &richer, vector<int> &quiet) {
        int n = quiet.size();
        vector<vector<int>> g(n);
        for (auto &r : richer) {
            g[r[1]].emplace_back(r[0]);
        }

        vector<int> ans(n, -1);
        function<void(int)> dfs = [&](int x) {
            if (ans[x] != -1) {
                return;
            }
            ans[x] = x;
            for (int y : g[x]) {
                dfs(y);
                if (quiet[ans[y]] < quiet[ans[x]]) {
                    ans[x] = ans[y];
                }
            }
        };
        for (int i = 0; i < n; ++i) {
            dfs(i);
        }
        return ans;
    }
};

[sol1-Java]

class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<Integer>();
        }
        for (int[] r : richer) {
            g[r[1]].add(r[0]);
        }

        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        for (int i = 0; i < n; ++i) {
            dfs(i, quiet, g, ans);
        }
        return ans;
    }

    public void dfs(int x, int[] quiet, List<Integer>[] g, int[] ans) {
        if (ans[x] != -1) {
            return;
        }
        ans[x] = x;
        for (int y : g[x]) {
            dfs(y, quiet, g, ans);
            if (quiet[ans[y]] < quiet[ans[x]]) {
                ans[x] = ans[y];
            }
        }
    }
}

[sol1-C#]

public class Solution {
    public int[] LoudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.Length;
        IList<int>[] g = new List<int>[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new List<int>();
        }
        foreach (int[] r in richer) {
            g[r[1]].Add(r[0]);
        }

        int[] ans = new int[n];
        Array.Fill(ans, -1);
        for (int i = 0; i < n; ++i) {
            DFS(i, quiet, g, ans);
        }
        return ans;
    }

    public void DFS(int x, int[] quiet, IList<int>[] g, int[] ans) {
        if (ans[x] != -1) {
            return;
        }
        ans[x] = x;
        foreach (int y in g[x]) {
            DFS(y, quiet, g, ans);
            if (quiet[ans[y]] < quiet[ans[x]]) {
                ans[x] = ans[y];
            }
        }
    }
}

[sol1-Golang]

func loudAndRich(richer [][]int, quiet []int) []int {
    n := len(quiet)
    g := make([][]int, n)
    for _, r := range richer {
        g[r[1]] = append(g[r[1]], r[0])
    }

    ans := make([]int, n)
    for i := range ans {
        ans[i] = -1
    }
    var dfs func(int)
    dfs = func(x int) {
        if ans[x] != -1 {
            return
        }
        ans[x] = x
        for _, y := range g[x] {
            dfs(y)
            if quiet[ans[y]] < quiet[ans[x]] {
                ans[x] = ans[y]
            }
        }
    }
    for i := 0; i < n; i++ {
        dfs(i)
    }
    return ans
}

[sol1-JavaScript]

var loudAndRich = function(richer, quiet) {
    const n = quiet.length;
    const g = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        g[i] = [];
    }
    for (const r of richer) {
        g[r[1]].push(r[0]);
    }

    const ans = new Array(n).fill(-1);
    for (let i = 0; i < n; ++i) {
        dfs(i, quiet, g, ans);
    }
    return ans;
};

const dfs = (x, quiet, g, ans) => {
    if (ans[x] !== -1) {
        return;
    }
    ans[x] = x;
    for (const y of g[x]) {
        dfs(y, quiet, g, ans);
        if (quiet[ans[y]] < quiet[ans[x]]) {
            ans[x] = ans[y];
        }
    }
}

[sol1-C]

void dfs(int x, const int* quiet, const int** graph, const int* graphColSize, int* ans) {
    if (ans[x] != -1) {
        return;
    }
    ans[x] = x;
    for (int i = 0; i < graphColSize[x]; ++i) {
        int y = graph[x][i];
        dfs(y, quiet, graph, graphColSize, ans);
        if (quiet[ans[y]] < quiet[ans[x]]) {
            ans[x] = ans[y];
        }
    }
}

int* loudAndRich(int** richer, int richerSize, int* richerColSize, int* quiet, int quietSize, int* returnSize){
    int** graph = (int **)malloc(sizeof(int *) * quietSize);
    int* graphColSize = (int *)malloc(sizeof(int) * quietSize);
    int* ans = (int *)malloc(sizeof(int) * quietSize);

    for (int i = 0; i < quietSize; ++i) {
        graph[i] = (int *)malloc(sizeof(int) * quietSize);
        ans[i] = -1;
        graphColSize[i] = 0; 
    }
    for (int i = 0; i < richerSize; ++i) {
        int x = richer[i][0];
        int y = richer[i][1];
        graph[y][graphColSize[y]] = x;
        graphColSize[y]++;
    }
    for (int i = 0; i < quietSize; ++i) {
        dfs(i, quiet, graph, graphColSize, ans);
    }
    for (int i = 0; i < quietSize; ++i) {
        free(graph[i]);
    }
    free(graphColSize);
    *returnSize = quietSize;
    return ans;
}

复杂度分析

• 时间复杂度：O(n+m)，其中 n 是数组 quiet 的长度，m 是数组 richer 的长度。建图和 DFS 的时间复杂度均为 O(n+m)。

• 空间复杂度：O(n+m)。我们需要 O(n+m) 的空间来记录图中所有的点和边。

方法二：拓扑排序

我们可以将方法一中的图的边全部反向，即如果 a_i 比 b_i 更有钱，我们从 a_i 向 b_i 连一条有向边。

这同样得到的是一张有向无环图，因此我们从图上任意一点（设为 x）出发，沿着有向边所能访问到的点，拥有的钱都比 x 少。这意味着我们可以在计算出 answer}[x] 后，用 answer}[x] 去更新 x 所能访问到的点的 answer 值。

要实现这一算法，我们可以将每个 answer}[x] 初始化为 x，然后对这张图执行一遍拓扑排序，并按照拓扑序去更新 x 的邻居的 answer 值。通过这一方式我们就能将 answer}[x] 的值「传播」到 x 所能访问到的点上。

[sol2-Python3]

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

[sol2-C++]

class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>> &richer, vector<int> &quiet) {
        int n = quiet.size();
        vector<vector<int>> g(n);
        vector<int> inDeg(n);
        for (auto &r : richer) {
            g[r[0]].emplace_back(r[1]);
            ++inDeg[r[1]];
        }

        vector<int> ans(n);
        iota(ans.begin(), ans.end(), 0);
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (inDeg[i] == 0) {
                q.emplace(i);
            }
        }
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int y : g[x]) {
                if (quiet[ans[x]] < quiet[ans[y]]) {
                    ans[y] = ans[x]; // 更新 x 的邻居的答案
                }
                if (--inDeg[y] == 0) {
                    q.emplace(y);
                }
            }
        }
        return ans;
    }
};

[sol2-Java]

class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<Integer>();
        }
        int[] inDeg = new int[n];
        for (int[] r : richer) {
            g[r[0]].add(r[1]);
            ++inDeg[r[1]];
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = i;
        }
        Queue<Integer> q = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            if (inDeg[i] == 0) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            int x = q.poll();
            for (int y : g[x]) {
                if (quiet[ans[x]] < quiet[ans[y]]) {
                    ans[y] = ans[x]; // 更新 x 的邻居的答案
                }
                if (--inDeg[y] == 0) {
                    q.offer(y);
                }
            }
        }
        return ans;
    }
}

[sol2-C#]

public class Solution {
    public int[] LoudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.Length;
        IList<int>[] g = new List<int>[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new List<int>();
        }
        int[] inDeg = new int[n];
        foreach (int[] r in richer) {
            g[r[0]].Add(r[1]);
            ++inDeg[r[1]];
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = i;
        }
        Queue<int> q = new Queue<int>();
        for (int i = 0; i < n; ++i) {
            if (inDeg[i] == 0) {
                q.Enqueue(i);
            }
        }
        while (q.Count > 0) {
            int x = q.Dequeue();
            foreach (int y in g[x]) {
                if (quiet[ans[x]] < quiet[ans[y]]) {
                    ans[y] = ans[x]; // 更新 x 的邻居的答案
                }
                if (--inDeg[y] == 0) {
                    q.Enqueue(y);
                }
            }
        }
        return ans;
    }
}

[sol2-Golang]

func loudAndRich(richer [][]int, quiet []int) []int {
    n := len(quiet)
    g := make([][]int, n)
    inDeg := make([]int, n)
    for _, r := range richer {
        g[r[0]] = append(g[r[0]], r[1])
        inDeg[r[1]]++
    }

    ans := make([]int, n)
    for i := range ans {
        ans[i] = i
    }
    q := make([]int, 0, n)
    for i, deg := range inDeg {
        if deg == 0 {
            q = append(q, i)
        }
    }
    for len(q) > 0 {
        x := q[0]
        q = q[1:]
        for _, y := range g[x] {
            if quiet[ans[x]] < quiet[ans[y]] {
                ans[y] = ans[x] // 更新 x 的邻居的答案
            }
            inDeg[y]--
            if inDeg[y] == 0 {
                q = append(q, y)
            }
        }
    }
    return ans
}

[sol2-JavaScript]

var loudAndRich = function(richer, quiet) {
    const n = quiet.length;
    const g = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        g[i] = [];
    }
    const inDeg = new Array(n).fill(0);
    for (const r of richer) {
        g[r[0]].push(r[1]);
        ++inDeg[r[1]];
    }

    const ans = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        ans[i] = i;
    }
    const q = [];
    for (let i = 0; i < n; ++i) {
        if (inDeg[i] === 0) {
            q.push(i);
        }
    }
    while (q.length) {
        const x = q.shift();
        for (const y of g[x]) {
            if (quiet[ans[x]] < quiet[ans[y]]) {
                ans[y] = ans[x]; // 更新 x 的邻居的答案
            }
            if (--inDeg[y] === 0) {
                q.push(y);
            }
        }
    }
    return ans;
};

复杂度分析

• 时间复杂度：O(n+m)，其中 n 是数组 quiet 的长度，m 是数组 richer 的长度。建图和拓扑排序的时间复杂度均为 O(n+m)。

• 空间复杂度：O(n+m)。我们需要 O(n+m) 的空间来记录图中所有的点和边。