> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/dfs/loud-and-rich.md).

# Loud and Rich

In a group of N people (labelled`0, 1, 2, ..., N-1`), each person has different amounts of money, and different levels of quietness.

For convenience, we'll call the person with label`x`, simply "person`x`".

We'll say that`richer[i] = [x, y]`if person`x` definitely has more money than person `y`. Note that`richer` may only be a subset of valid observations.

Also, we'll say`quiet[x] = q`if personx has quietness`q`.

Now, return`answer`, where`answer[x] = y`if`y`is the least quiet person (that is, the person`y`with the smallest value of`quiet[y]`), among all people who definitely have equal to or more money than person`x`.

**Example 1:**

```
Input: 
richer = 
[[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]]
, quiet = 
[3,2,5,4,6,1,7,0]
Output: 
[5,5,2,5,4,5,6,7]
Explanation: 

answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but
it isn't clear if they have more money than person 0.

answer[7] = 7.
Among all people that definitely have equal to or more money than person 7
(which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x])
is person 7.

The other answers can be filled out with similar reasoning.
```

**Note:**

```
1 <= quiet.length = N <= 500
0 <= quiet[i] < N, all quiet[i] are different.
0 <= richer.length <= N * (N-1) / 2
0 <= richer[i][j] < N
richer[i][0] != richer[i][1]
richer[i]'s are all different.
The observations in richer are all logically consistent.
```

分析

DFS建图，比自己大的放list。dfs list里选quiet最小的。也是带memo的

简缩版

```
class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        g = collections.defaultdict(list)
        for u,v in richer:
            g[v].append(u)
        n = len(quiet)
        res = [-1]*n

        def dfs(i):
            if res[i] < 0:            
                res[i] = min([dfs(j) for j in g[i]] + [i], key = lambda x: quiet[x]) #不要忘了Key，也不要忘了加[i]自己。
            return res[i]
        return list(map(dfs, range(n))) #dfs没有()
```

扩展板DFS

```
class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        g = collections.defaultdict(list)
        for u,v in richer:
            g[v].append(u)
        n = len(quiet)
        res = [-1]*n

        def dfs(i):
            if res[i] >= 0: 
                return res[i]
            res[i] = i
            for j in g[i]:
                if quiet[res[i]] > quiet[dfs(j)]:
                    res[i] = res[j]
            return res[i]
        return list(map(dfs, range(n))) #dfs没有()
```

BFS

富点跟一串穷点。富点入度0，topo排序

res\[]里指向的是比他富切比他安静的人

```
class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        g = collections.defaultdict(list)
        indegree = collections.defaultdict(int)
        for u,v in richer:
            g[u].append(v)
            indegree[v] += 1
        n = len(quiet)
        res = [i for i in range(n)] #初始赋值为点本身
        q = [i for i in range(n) if indegree[i] == 0]
        while q:
            cur = q.pop()
            for nxt in g[cur]:
                if quiet[res[nxt]] > quiet[res[cur]]:#quiet[res[nxt]]  不是直接quiet[nxt] 
                         res[nxt] = res[cur]
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    q.append(nxt)
        return res
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/dfs/loud-and-rich.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.