leetcode 851. Loud and Rich 喧闹和富有-耗时100%

Problem: 851. Loud and Rich 喧闹和富有

解题过程

耗时100%，最开始用深度优先搜索小的指向大的，可以做但是超时了

逆向思考以后，由大的指向小的tr[richer[i][0]].push_back(richer[i][1]);，使用了拓扑排序的，计算入度，将入度0的放入队列，每次计算入度0的节点指向的节点的quiet最小的索引

Code

class Solution { public: vector<int> ret; vector<bool> status; vector<vector<int>> tr; int mi = INT_MAX; vector<int> qt; int dfs(int start) { // status[start] = true; int next; if(tr[start].size() == 0) { ret[start] = start; // status[start] = false; return start; } int mimi = qt[start], ans, id = start; for(int i = 0; i < tr[start].size(); i++) { next = tr[start][i]; // if(status[next] == false) { if(tr[next].size() == 0) { ans = next; } else { ans = dfs(next); } if(mimi > qt[ans]) { id = ans; mimi = qt[ans]; } // } } // status[start] = false; ret[start] = id; return id; } vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) { // int n = quiet.size(); // tr.resize(n); // for(int i = 0; i < richer.size(); i++) { // tr[richer[i][1]].push_back(richer[i][0]); // } // ret.assign(n, INT_MAX); // status.assign(n, false); // qt = std::move(quiet); // for(int i = 0; i < n; i++) { // if(tr[i].size() == 0) ret[i] = i; // } // for(int i = 0; i < n; i++) { // if(ret[i]==INT_MAX) { // dfs(i); // } // } // return ret; int n = quiet.size(); ret.resize(n); status.assign(n, false); tr.resize(n); for(int i = 0; i < richer.size(); i++) { tr[richer[i][0]].push_back(richer[i][1]); } vector<int> degree(n, 0); for(int i = 0; i < n; i++) { for(int j = 0; j < tr[i].size(); j++) { degree[tr[i][j]]++; } } queue<int> qe; for(int i = 0; i < n; i++) { if(degree[i] == 0) { qe.push(i); status[i] = true; } ret[i] = i; } int ind, kw, par; while( !qe.empty() ) { ind = qe.front(); qe.pop(); for(int i = 0; i < tr[ind].size(); i++) { kw = tr[ind][i]; par = ret[ind]; if(quiet[par] < quiet[ret[kw]]) { ret[kw] = par; } degree[kw]--; if(degree[kw] == 0 && status[kw] == false) { qe.push(kw); } } } return ret; } };