851. Loud and Rich
题目链接:https://leetcode.com/problems/loud-and-rich/description/
思路:有向图DFS,记录最小的quiet值
注意点:可优化,记忆性搜索,每次搜到已经记录过的值时可直接比较不需要进一步搜下去。
1 void DFS(vector<int> &visited, vector<vector<int> >& G, int x,vector<int>& quiet, int &res,int &minid){
2 visited[x] = 1;
3 if(res > quiet[x]){
4 res = quiet[x];
5 minid = x;
6 }
7 for(auto i:G[x]){
8 if(visited[i] == 0){
9 DFS(visited,G,i,quiet,res,minid);
10 }
11 }
12 return;
13 }
14 vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
15 vector<int> ans;
16 int n = quiet.size();
17 vector<vector<int> > G;
18 G.resize(n);
19 for(auto i : richer){
20 G[i[1]].push_back(i[0]);
21 }
22 vector<int> visited;
23
24 for(int i = 0 ; i < n; i++){
25 int res = 100000;
26 int minid = -1;
27 visited.assign(n,0);
28 DFS(visited,G,i,quiet,res,minid);
29 ans.push_back(minid);
30 }
31 return ans;
32 }