# Leetcode 851 - Loud and Rich

`Note:`

`Topological BFS:`

- Looks at the input, it’s quite like the
`course schedule`

problem I did. Using`indegree`

gives us access to traverse the graph. - Be careful of the direction of edges. It has to point from
`richer`

to`poorer`

because in`ans`

, the richest people have their own as the answer. - Construct a
`map`

for`edges`

, and initialize`queue`

with vertexes whose`indegree === 0`

. - While iterating, update
`queue`

with`vertex`

whose`indegree`

becomes`0`

.

- Looks at the input, it’s quite like the
`DFS:`

- DFS was my first intuition but I didn’t think it thorough. (sad)
- Use
`ans[]`

to memo answers. - Use
`map`

to construct`edges`

from`poor`

to`rich`

. - Do DFS toward every possible edges.
- Return ans when
`ans[i]`

is not -1. - For richest people, return themselves.

`Question:`

There is a group of `n`

people labeled from `0`

to `n - 1`

where each person has a different amount of money and a different level of quietness.

You are given an array `richer`

where `richer[i] = [ai, bi]`

indicates that `ai`

has more money than `bi`

and an integer array `quiet`

where `quiet[i]`

is the quietness of the `ith`

person. All the given data in richer are logically correct (i.e., the data will not lead you to a situation where `x`

is richer than `y`

and `y`

is richer than `x`

at the same time).

Return an integer array `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 the 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] |

`Code:`

`Topological sort`

1 | /** |

`DFS`

1 | /** |