题目
有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。
给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自恰（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 ）。
现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。
示例 1：
输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0] 输出：[5,5,2,5,4,5,6,7] 解释： answer[0] = 5， person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。 唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7， 但是目前还不清楚他是否比 person 0 更有钱。 answer[7] = 7， 在所有拥有的钱肯定不少于 person 7 的人中（这可能包括 person 3，4，5，6 以及 7）， 最安静（有较低安静值 quiet[x]）的人是 person 7。 其他的答案也可以用类似的推理来解释。
示例 2：
输入：richer = [], quiet = [0] 输出：[0]
解题
这道题的意思，就是找比当前这个人(顶点)有钱的，并且最低调的人(顶点)作为answer。
方法一：拓扑排序
如果a比b更有钱，那么可以从a向b连一条有向边
可以通过richer构造一张有向图
举个例子：
假设要比较获得D的answer
如下图可以看出，A,B,C都比D有钱。
比较的时候，C连接D，比较C是否比D更加安静。
B连接D，比较B是否比D更加安静(实际上，这一步之前，就比较了A与B，B的answer就是 A与B最安静的那个)
因此相邻之间的比较，对于D来说，answer就相当于与A、B、C、D中最安静的那个。
class Solution { public: vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) { int n=quiet.size(); vector<vector<int>> g(n); vector<int> inDeg(n); //建立邻接表 for(vector<int>& r:richer){ g[r[0]].push_back(r[1]); inDeg[r[1]]++; } //初始化answer vector<int> res(n); iota(res.begin(),res.end(),0); //初始化queue，加入入度为0的 queue<int> q; for(int i=0;i<n;i++){ if(inDeg[i]==0) q.push(i); } //拓扑排序 while(!q.empty()){ int x=q.front(); q.pop(); for(int y:g[x]){ if(quiet[res[x]]<quiet[res[y]]){ res[y]=res[x]; } if(--inDeg[y]==0){ q.push(y); } } } return res; } };
方法二：深度优先搜索+记忆化递归
构造反向图，如果a大于b，那么可以从b向a连一条有向边。
使用dfs和res进行记忆化递归，复杂度低。
class Solution { public: vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) { int n=quiet.size(); vector<vector<int>> g(n); //构造邻接表 for(vector<int>& r:richer){ g[r[1]].push_back(r[0]); } //初始化，-1代表没访问过 vector<int> res(n,-1); //图遍历：DFS function<void(int)> dfs=[&](int x){ if(res[x]!=-1) return;//防止顶点重复遍历 res[x]=x; for(int y:g[x]){ dfs(y); if(quiet[res[y]]<quiet[res[x]]){ res[x]=res[y]; } } }; //保证每个顶点都遍历过 for(int i=0;i<n;i++){ dfs(i); } return res; } };
