2021.12.15 - 178.喧闹和富有

1. 题目

2. 思路

(1) DFS

• 根据richer可以构建出有向无环图，从任意一点出发，所能到达的点都是比起始点富有的点。
• 每个点的默认答案是其本身，利用深度优先搜索遍历比其富有的点，若比其富有的点同时比其安静，则更新其答案。

3. 代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Test {public static void main(String[] args) {}
}class Solution {private List<Integer>[] list;private int[] res;private int[] quiet;public int[] loudAndRich(int[][] richer, int[] quiet) {int n = quiet.length;list = new List[n];res = new int[n];this.quiet = quiet;for (int i = 0; i < n; i++) {list[i] = new ArrayList<>();}for (int[] ints : richer) {list[ints[1]].add(ints[0]);}Arrays.fill(res, -1);for (int i = 0; i < n; i++) {dfs(i);}return res;}private void dfs(int i) {if (res[i] != -1) {return;}res[i] = i;for (Integer j : list[i]) {dfs(j);if (quiet[res[j]] < quiet[res[i]]) {res[i] = res[j];}}}
}