3310.移除可疑的方法：深度优先搜索(DFS)

【LetMeFly】3310.移除可疑的方法：深度优先搜索(DFS)

力扣题目链接：https://leetcode.cn/problems/remove-methods-from-project/

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

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

已知如果方法 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 <= 105
• 0 <= k <= n - 1
• 0 <= invocations.length <= 2 * 105
• invocations[i] == [ai, bi]
• 0 <= ai, bi <= n - 1
• ai != bi
• invocations[i] != invocations[j]

解题方法：深度优先搜索

首先遍历一遍所有边并得到邻接表，接着从节点$k$开始深度优先搜索，谁被指到谁可疑。

再遍历一遍所有边，看看有没有好节点指向坏节点的边，如果有，直接返回$0$到$n-1$；否则，返回所有可疑节点。

• 时间复杂度$O(n+m)$，其中$m=len(invocations)$
• 空间复杂度$O(n+m)$

AC代码

C++

/*
 * @LastEditTime: 2026-08-05 21:43:40
 */
class Solution {
private:
    vector<bool> visited;
    vector<vector<int>> graph;

    void dfs(int from) {
        visited[from] = true;
        for (int to : graph[from]) {
            if (!visited[to]) {
                dfs(to);
            }
        }
    }
public:
    vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
        graph.resize(n);
        for (vector<int>& i : invocations) {
            graph[i[0]].push_back(i[1]);
        }

        visited.resize(n);
        dfs(k);

        for (vector<int>& i : invocations) {
            if (!visited[i[0]] && visited[i[1]]) {
                vector<int> ans(n);
                iota(ans.begin(), ans.end(), 0);
                return ans;
            }
        }

        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源