3310. 移除可疑的方法（2026.08.05）
题目描述
你正在维护一个项目，该项目有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^50 <= k <= n - 10 <= invocations.length <= 2 * 10^5invocations[i] == [a_i, b_i]0 <= a_i, b_i <= n - 1a_i != b_iinvocations[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;}};