发表于 2024.05.15

• 首先使用图论将问题抽象出来，将人视作为节点。可以采用DFS的方法解决问题：首先如果a比b富有，则添加有向边b -> a(注意是指向更富的人)，然后通过DFS的方法，求解节点a中，比a富有的人中，quiet值最小的人：首先初始化quiet最小者为自己，然后遍历子节点中quiet值最小者，更新自身的最优解，直至所有节点处理完毕。

  同样，此类涉及入度出度的问题可以转化为拓扑排序：如果a比b富有，则添加有向边a -> b(注意这里是指向更穷的人)。不难得知，入度为0的节点意味着没有人比他富有，即属于最富的一批人。但不能使用前缀和的思路解决，因为最富的一批人中，我们不知道他们内部谁比谁有钱(没有边连接他们)。所以，我们可以在拓扑排序的过程中，当处理入度已为0的节点u时，减少其子节点v的入度过程中，顺带更新v中quiet值最小者的数据。这种本质就是从富有到贫穷的顺序开始处理，不断更新穷人(子节点)的数据。

  使用DFS的做法：

  from collections import deque
  
  
  class Solution:
      def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
          n = len(quiet)
          adj_list = [[] for _ in range(n)]
          for u, v in richer:
              adj_list[v].append(u)  # v -> u 指向更有钱的人
  
          ans = [-1] * n
  
          def dfs(u: int) -> int:
              nonlocal ans
              if ans[u] != -1:
                  return ans[u]
  
              min_quiet_people = u
              for v in adj_list[u]:
                  min_quiet_people_from_v = dfs(v)
                  if quiet[min_quiet_people_from_v] < quiet[min_quiet_people]:
                      min_quiet_people = min_quiet_people_from_v
              ans[u] = min_quiet_people
              return min_quiet_people
  
          for u in range(n):
              if ans[u] == -1:
                  dfs(u)
  
          return ans

  使用拓扑排序的做法：

  from collections import deque
  
  
  class Solution:
      def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
          # 拓扑排序: 如果没有人比你有钱 那你就是最有钱的
          n = len(quiet)
          in_degree = [0] * n
          adj_list = [[] for _ in range(n)]
          for u, v in richer:
              adj_list[u].append(v)  # u -> v u比v有钱
              in_degree[v] += 1
          
          q = deque()
          # 获取最有钱的一批人
          for i in range(n):
              if in_degree[i] == 0:  # 没有入度的 -> 没有比它有钱的
                  q.append(i)
  
          ans = list(range(n))
  
          while q:
              u = q.popleft()
  
              for v in adj_list[u]:
                  in_degree[v] -= 1
                  # 在减少入度的时候，顺便更新子节点的数据
                  if quiet[ans[v]] > quiet[ans[u]]:
                      ans[v] = ans[u]
                  if in_degree[v] == 0:
                      q.append(v)
          return ans

• LC 题目链接