# 851. Loud and Rich¶

• Time: $O(|V| + |E|)$, where $|V| = |\texttt{quiet}|$ and $|E| = |\texttt{richer}|$
• Space: $O(|V| + |E|)$
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public: vector loudAndRich(vector>& richer, vector& quiet) { const int n = quiet.size(); vector ans(n, -1); vector> graph(n); for (const vector& r : richer) { const int u = r[1]; const int v = r[0]; graph[u].push_back(v); } for (int i = 0; i < n; ++i) dfs(graph, i, quiet, ans); return ans; } private: int dfs(const vector>& graph, int u, const vector& quiet, vector& ans) { if (ans[u] != -1) return ans[u]; ans[u] = u; for (const int v : graph[u]) { const int res = dfs(graph, v, quiet, ans); if (quiet[res] < quiet[ans[u]]) ans[u] = res; } return ans[u]; } };
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public int[] loudAndRich(int[][] richer, int[] quiet) { final int n = quiet.length; int[] ans = new int[n]; List[] graph = new List[n]; Arrays.fill(ans, -1); for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int[] r : richer) { final int u = r[1]; final int v = r[0]; graph[u].add(v); } for (int i = 0; i < n; ++i) dfs(graph, i, quiet, ans); return ans; } private int dfs(List[] graph, int u, int[] quiet, int[] ans) { if (ans[u] != -1) return ans[u]; ans[u] = u; for (final int v : graph[u]) { final int res = dfs(graph, v, quiet, ans); if (quiet[res] < quiet[ans[u]]) ans[u] = res; } return ans[u]; } }
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]: graph = [[] for _ in range(len(quiet))] for v, u in richer: graph[u].append(v) @functools.lru_cache(None) def dfs(u: int) -> int: ans = u for v in graph[u]: res = dfs(v) if quiet[res] < quiet[ans]: ans = res return ans return map(dfs, range(len(graph)))