M3310.移除可疑的方法

bfs, 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 <= 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]

这道题可以通过 图的遍历（BFS/DFS） 来解决。

解题思路

寻找所有可疑方法：
- 题目定义：方法 k 以及从方法 k 直接或间接调用的所有方法均为“可疑方法”。
- 我们可以根据 invocations 建立邻接表 $u \to v$ （表示 $u$ 调用了 $v$ ）。
- 从节点 k 出发进行广度优先搜索（BFS）或深度优先搜索（DFS），记录所有能到达的节点，这些节点构成了 可疑方法集合 suspicious。
检查移除条件：
- 题目要求：“只有当这组可疑方法没有被这组之外的任何方法调用时，才能被移除”。
- 遍历 invocations 中的所有调用关系 $[u, v]$ ：
  - 如果 $u$ 不在可疑方法集合中（ $u \notin suspicious$ ），而 $v$ 在可疑方法集合中（ $v \in suspicious$ ），说明外部有方法调用了可疑方法，不满足移除条件。
  - 此时 无法移除任何方法，直接返回所有方法：[0, 1, ..., n-1]。
构造最终答案：
- 如果检查后没有发现上述非法调用，说明可疑方法可以被安全移除。
- 返回所有不在可疑方法集合中的方法。

Python 代码实现

python

from collections import deque
from typing import List

class Solution:
    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
        # 1. 构建图的邻接表：adj[u] 包含 u 调用的所有方法 v
        adj = [[] for _ in range(n)]
        for u, v in invocations:
            adj[u].append(v)
        
        # 2. 从 k 出发进行 BFS，找出所有可疑方法
        suspicious = set([k])
        queue = deque([k])
        
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if v not in suspicious:
                    suspicious.add(v)
                    queue.append(v)
        
        # 3. 检查是否有“非可疑方法”调用了“可疑方法”
        for u, v in invocations:
            if u not in suspicious and v in suspicious:
                # 存在外部方法调用了可疑方法，无法移除，返回所有方法
                return list(range(n))
        
        # 4. 如果可以安全移除，返回剩余的方法
        return [i for i in range(n) if i not in suspicious]

复杂度分析

时间复杂度： $O (n + m)$ ，其中 $n$ 为方法数量， $m$ 为调用关系数量 invocations.length。
- 构建邻接表需要 $O (m)$ 。
- BFS 遍历可疑方法最多访问 $n$ 个节点和 $m$ 条边，复杂度为 $O (n + m)$ 。
- 检查合法性遍历所有边需要 $O (m)$ 。
- 生成最终列表需要 $O (n)$ 。
- 整体耗时极优，可在规定时间内轻松通过 $n \leq 10^{5}, m \leq 2 \times 10^{5}$ 的测试用例。
空间复杂度： $O (n + m)$ 。
- 邻接表需要 $O (n + m)$ 的空间。
- BFS 的队列和 suspicious 集合需要 $O (n)$ 的空间。

M3310.移除可疑的方法 ​

M3310.移除可疑的方法