851. Loud and Rich —— weekly contest 87

851. Loud and Rich

题目链接：https://leetcode.com/problems/loud-and-rich/description/

思路：有向图DFS,记录最小的quiet值

注意点：可优化，记忆性搜索，每次搜到已经记录过的值时可直接比较不需要进一步搜下去。

1 1 void DFS(vector<int> &visited, vector<vector<int> >& G, int x,vector<int>& quiet, int &res,int &minid){
2 2         visited[x] = 1;
3 3         if(res > quiet[x]){
4 4             res = quiet[x];
5 5             minid = x;
6 6         }
7 7         for(auto i:G[x]){
8 8             if(visited[i] == 0){
9 9                 DFS(visited,G,i,quiet,res,minid);
1010             }
1111         }
1212         return;
1313     }
1414     vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
1515         vector<int> ans;
1616         int n = quiet.size();
1717         vector<vector<int> > G;
1818         G.resize(n);
1919         for(auto i : richer){
2020             G[i[1]].push_back(i[0]);
2121         }
2222         vector<int> visited;
2323         
2424         for(int i = 0 ; i < n; i++){
2525             int res = 100000;
2626             int minid = -1;
2727             visited.assign(n,0);
2828             DFS(visited,G,i,quiet,res,minid);
2929             ans.push_back(minid);
3030         }
3131         return ans;
3232     }