题目描述

你正在维护一个项目，该项目有n个方法，编号从0到n - 1。

给你两个整数n和k，以及一个二维整数数组invocations，其中invocations[i] = [a_i, b_i]表示方法a_i调用了方法b_i。

已知如果方法k存在一个已知的 bug。那么方法k以及它直接或间接调用的任何方法都被视为可疑方法，我们需要从项目中移除这些方法。

只有当一组方法没有被这组之外的任何方法调用时，这组方法才能被移除。

返回一个数组，包含移除所有可疑方法后剩下的所有方法。你可以以任意顺序返回答案。如果无法移除所有可疑方法，则不移除任何方法。

示例 1:

输入:n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]]

输出:[0,1,2,3]

解释:

方法 2 和方法 1 是可疑方法，但它们分别直接被方法 3 和方法 0 调用。由于方法 3 和方法 0 不是可疑方法，我们无法移除任何方法，故返回所有方法。

示例 2:

输入:n = 5, k = 0, invocations = [[1,2],[0,2],[0,1],[3,4]]

输出:[3,4]

解释:

方法 0、方法 1 和方法 2 是可疑方法，且没有被任何其他方法直接调用。我们可以移除它们。

示例 3:

输入:n = 3, k = 2, invocations = [[1,2],[0,1],[2,0]]

输出:[]

解释:

所有方法都是可疑方法。我们可以移除它们。

提示

• 1 <= n <= 10^5
• 0 <= k <= n - 1
• 0 <= invocations.length <= 2 * 10^5
• invocations[i] == [a_i, b_i]
• 0 <= a_i, b_i <= n - 1
• a_i != b_i
• invocations[i] != invocations[j]

苯人思路

先找出所有可疑方法，再看是否有其他方法调用可疑方法

通过率 691 / 775，会超时

classSolution{public:vector<int>remainingMethods(intn,intk,vector<vector<int>>&invocations){if(invocations.empty()){vector<int>answer(n);iota(answer.begin(),answer.end(),0);answer.erase(answer.begin()+k);returnanswer;}vector<int>suspicious(n,0);sort(invocations.begin(),invocations.end());suspicious[k]=1;vector<int>redis={k};// redis记录: 未遍历过的作为调用者的可疑方法// 构造可疑方法数组suspicious// suspicious值为1即为可疑方法while(!redis.empty()){inttemp=redis[0];// 取出第一个未遍历过的作为调用者的可疑方法for(auto&x:invocations){if(x[0]>temp){redis.erase(redis.begin());break;}elseif(x[0]==temp){if(suspicious[x[1]]==1){if(x!=invocations.back())continue;}else{suspicious[x[1]]=1;redis.emplace_back(x[1]);}}if(x==invocations.back()){redis.erase(redis.begin());break;}}}// 再次遍历,检查可疑方法是否被其他方法调用boolflag=false;for(auto&x:invocations){if(suspicious[x[0]]==0&&suspicious[x[1]]==1){flag=true;break;}}if(flag){vector<int>answer(n);iota(answer.begin(),answer.end(),0);returnanswer;}else{vector<int>answer;for(inti=0;i<n;i++){if(suspicious[i]!=1)answer.emplace_back(i);}returnanswer;}}};

优化——二分查找

思路不变，对实现方法进行了一些优化

classSolution{public:vector<int>remainingMethods(intn,intk,vector<vector<int>>&invocations){sort(invocations.begin(),invocations.end());vector<int>suspicious(n,0);suspicious[k]=1;queue<int>q;q.push(k);// BFS 找出所有可疑方法while(!q.empty()){intcaller=q.front();q.pop();// 使用二分查找找到第一个 caller == 当前值的位置// lower_bound查找第一个不小于给定值(vector<int>{caller, -1})的元素位置autoit=lower_bound(invocations.begin(),invocations.end(),vector<int>{caller,-1});while(it!=invocations.end()&&(*it)[0]==caller){intcallee=(*it)[1];if(!suspicious[callee]){suspicious[callee]=1;q.push(callee);}it++;}}// 检查是否有非可疑方法调用了可疑方法boolhasExternalCall=false;for(auto&inv:invocations){if(!suspicious[inv[0]]&&suspicious[inv[1]]){hasExternalCall=true;break;}}// 构造结果vector<int>answer;if(hasExternalCall){for(inti=0;i<n;i++){answer.push_back(i);}}else{for(inti=0;i<n;i++){if(!suspicious[i]){answer.push_back(i);}}}returnanswer;}};

标准做法——邻接表

classSolution{public:vector<int>remainingMethods(intn,intk,vector<vector<int>>&invocations){// 构建邻接表vector<vector<int>>graph(n);for(auto&inv:invocations){graph[inv[0]].push_back(inv[1]);}// BFS 标记可疑方法vector<int>suspicious(n,0);queue<int>q;q.push(k);suspicious[k]=1;while(!q.empty()){intcurr=q.front();q.pop();for(intnext:graph[curr]){if(!suspicious[next]){suspicious[next]=1;q.push(next);}}}// 检查是否有外部调用boolhasExternalCall=false;for(auto&inv:invocations){if(!suspicious[inv[0]]&&suspicious[inv[1]]){hasExternalCall=true;break;}}// 构造答案vector<int>answer;if(hasExternalCall){for(inti=0;i<n;i++)answer.push_back(i);}else{for(inti=0;i<n;i++){if(!suspicious[i])answer.push_back(i);}}returnanswer;}};