leetcode:喧闹和富有(dfs)

思路：
1.dfs
2.用rich_vector存着比自己有钱的人
3.ans为最终答案，初始为全-1
4.dfs(x)若ans已经找到则返回，若没有，则初始为自己(x),然后遍历所有的邻居，让邻居先找到邻居中最安静的，然后我们将ans(x)与所有邻居中最安静的结果进行比较，若发现更安静的则改变自己的答案
5.最后对所有节点来一次dfs

代码：

class Solution:def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:# 每个人存着直接比自己有钱的邻居# 深度优先遍历：最安静的人要么是自己# 要么是邻居中最安静的人（邻居就是比自己有钱的人）# 邻居的集合必然是比自己更有钱的人n = len(quiet)rich_vector = [ [] for _ in range(n)]# 从穷的指向富有的for r in richer:rich_vector[r[1]].append(r[0])# 记录结果的ansans = [-1] * n# dfsdef dfs(x):# 如果已经找到过了if ans[x] != -1:return# 初始化为自己ans[x] = x# 找邻居for neighbor in rich_vector[x]:dfs(neighbor)# 邻居中最安静的人找出来了if quiet[ans[neighbor]] < quiet[ans[x]]:ans[x] = ans[neighbor]# 每个人遍历一次for i in range(n):dfs(i)return ans

总结：
1.构建有向图进行dfs基本的套路