本文涉及知识点

C++图论
C++DFS

LeetCode851. 喧闹和富有

有一组 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]
提示：
n == quiet.length
1 <= n <= 500
0 <= quiet[i] < n
quiet 的所有值 互不相同
0 <= richer.length <= n * (n - 1) / 2
0 <= ai, bi < n
ai != bi
richer 中的所有数对 互不相同
对 richer 的观察在逻辑上是一致的

图论 后续DFS

确定和自己钱相等的，只有自己。
钱确定比自己多的。通过DFS求，临接边就是：richer[i][1]$\to$ richer[i][0] 。
由于是钱少的指向钱多的，故没有环， 可以用parent避免重复处理。由于一个节点可能有n个父节点，故用父节点除重时间复杂度可能上升n倍。
m_ans[cur]记录 各节点答案。m_quiet = quiet
DFS(cur,parent)
for(const auto& next : neiBo[cur]){
DFS(next,cur);
m_quiet[cur] = minSelf(m_ans[next])
}
m_ans 记录对应y。
时间复杂度：O(E) e = richer.length。
out[i]记录比钱比i少的人的数量，out[i]为0是树的根。
DFS各根。

代码

核心代码

class Solution {
		public:
			vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
				m_quiet = quiet;
				m_ans.resize(quiet.size());
				m_vis.resize(quiet.size());
				iota(m_ans.begin(), m_ans.end(), 0);
				const int N = quiet.size();
				vector<vector<int>> neiBo(N);
				vector<int> outer(N);
				for (const auto& v : richer) {
					neiBo[v[1]].emplace_back(v[0]);
					outer[v[0]]++;
				}	
				function<void(int)> DFS = [&](int cur) {
					if (m_vis[cur]) { return; }
					m_vis[cur] = true;
					for (const auto& next : neiBo[cur]) {						
						DFS(next);
						if (m_quiet[next] < m_quiet[cur]) {
							m_quiet[cur] = m_quiet[next];
							m_ans[cur] = m_ans[next];
						}
					}
				};
				for (int i = 0; i < N; i++) {
					if (outer[i] > 0) { continue; }
					DFS(i);
				}
				return m_ans;
			}
			vector<int> m_quiet,m_ans,m_vis;
		};

单元测试

vector<vector<int>> richer;
		vector<int> quiet;
		TEST_METHOD(TestMethod11)
		{
			richer = { {1,0},{2,1},{3,1},{3,7},{4,3},{5,3},{6,3} }, quiet = { 3,2,5,4,6,1,7,0 };
			auto res = Solution().loudAndRich(richer, quiet);
			AssertEx(vector<int>{ 5, 5, 2, 5, 4, 5, 6, 7}, res);
		}
		TEST_METHOD(TestMethod12)
		{
			richer = {  }, quiet = { 0 };
			auto res = Solution().loudAndRich(richer, quiet);
			AssertEx(vector<int>{ 0}, res);
		}