# 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.
• 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:

Code:

Topological sort

DFS