日期: 2026年8月5日

目标

你正在维护一个项目，该项目有 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 <= 10^5
• 0 <= k <= n - 1
• 0 <= invocations.length <= 2 * 10^5
• invocations[i] == [ai, bi]
• 0 <= ai, bi <= n - 1
• ai != bi
• invocations[i] != invocations[j]

思路

有 n 个方法，编号为 0 ~ n - 1，invocations[i] = [ai, bi] 表示方法 ai 调用了方法 bi。已知方法 k 是可疑的，所有被 k 直接或间接调用的方法也都是可疑的。这些可疑方法如果没有被其它非可疑方法调用可以全部移除，返回剩余的方法。

先标记 k 直接或间接调用的方法，再从所有非可疑方法出发，判断是否会调用可疑方法。如果会调用，不可移除，否则直接返回所有非可疑方法。

代码

/**
 * @date 2026-08-05 9:17
 */
public class RemainingMethods3310 {

    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, x -> new ArrayList<>());
        for (int[] i : invocations) {
            g[i[0]].add(i[1]);
        }
        boolean[] remove = new boolean[n];
        boolean[] visited = new boolean[n];
        dfs(k, g, remove);
        boolean canRemove = true;
        for (int i = 0; i < n; i++) {
            if (remove[i]) {
                continue;
            }
            if (dfs(i, g, visited, remove)) {
                canRemove = false;
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!canRemove) {
                res.add(i);
            } else if (!remove[i]) {
                res.add(i);
            }
        }
        return res;
    }

    public void dfs(int m, List<Integer>[] g, boolean[] remove) {
        if (remove[m]) {
            return;
        }
        remove[m] = true;
        for (Integer next : g[m]) {
            dfs(next, g, remove);
        }
    }

    public boolean dfs(int m, List<Integer>[] g, boolean[] visited, boolean[] remove) {
        visited[m] = true;
        if (remove[m]) {
            return true;
        }
        boolean res = false;
        for (Integer next : g[m]) {
            if (!visited[next]) {
                res = res || dfs(next, g, visited, remove);
            }
        }
        return res;
    }

}

性能