2025-05-06：移除可疑的方法。用go语言，你负责维护一个包含 n 个方法（编号从 0 到 n - 1）的项目。

已知方法 k 存在一个已知 bug。基于此，方法 k 以及所有被它直接或间接调用的方法都被视为有问题的方法，需要从项目中删除。

给定 n、k 和一个调用关系数组 invocations，其中每个元素 [ai, bi] 表示方法 ai 调用了方法 bi。
只有当一组待删除的方法不被其他非该组的方法调用时，才允许将这组方法全部移除。

请返回删除所有可疑方法后，项目中剩余的方法列表（顺序不限）。如果无法完成全部可疑方法的删除，则不做任何删除，返回所有原有方法。

1 <= n <= 100000。

0 <= k <= n - 1。

0 <= invocations.length <= 2 * 100000。

invocations[i] == [ai, bi]。

0 <= ai, bi <= n - 1。

ai != bi。

invocations[i] != invocations[j]。

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

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

解释:

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

题目来自leetcode3310。

分步骤描述过程：

1. 构建调用图：

   • 首先，根据给定的调用关系数组 invocations，构建一个有向图 g，其中每个节点代表一个方法，边 a -> b 表示方法 a 调用了方法 b。这里 g 是一个邻接表，g[x] 存储所有被方法 x 直接调用的方法。

2. 标记可疑方法：

   • 从已知的 bug 方法 k 开始，进行深度优先搜索（DFS）或类似的遍历，标记所有直接或间接被 k 调用的方法为可疑方法。具体来说：
     • 初始化一个布尔数组 isSuspicious，长度为 n，初始值为 false。
     • 从 k 开始 DFS，对于当前方法 x，标记 isSuspicious[x] = true，然后递归遍历 x 调用的所有方法 y。如果 y 未被标记为可疑，则继续 DFS。

3. 检查是否可以移除可疑方法：

   • 遍历所有调用关系 [a, b]，检查是否存在以下情况：
     • 调用者 a 不是可疑方法（isSuspicious[a] == false），但被调用的 b 是可疑方法（isSuspicious[b] == true）。
   • 如果存在这样的调用关系，说明至少有一个非可疑方法调用了可疑方法，此时无法移除任何可疑方法，直接返回所有方法 [0, 1, ..., n-1]。

4. 移除可疑方法：

   • 如果没有发现非可疑方法调用可疑方法的情况，则可以安全移除所有可疑方法。此时，遍历 isSuspicious 数组，将所有 isSuspicious[i] == false 的方法 i 加入结果列表。

5. 返回结果：

   • 根据上述检查的结果，返回剩余的方法列表或所有方法。

示例分析：

对于输入 n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]]：

1. 构建调用图：
   • g[1] = [2]（方法 1 调用方法 2）
   • g[0] = [1]（方法 0 调用方法 1）
   • g[3] = [2]（方法 3 调用方法 2）
2. 标记可疑方法：
   • 从 k = 1 开始 DFS：
     • 标记 isSuspicious[1] = true，然后遍历 g[1] = [2]。
     • 标记 isSuspicious[2] = true，g[2] 为空，结束。
   • 最终 isSuspicious = [false, true, true, false]（方法 1 和方法 2 是可疑的）。
3. 检查是否可以移除：
   • 检查所有调用关系：
     • [0,1]：0 不是可疑，1 是可疑 → 无法移除。
   • 因此直接返回 [0, 1, 2, 3]。

时间复杂度和空间复杂度：

• 时间复杂度：
  • 构建调用图：遍历 invocations，时间复杂度为 O(M)，其中 M 是 invocations 的长度。
  • 标记可疑方法：DFS 或 BFS 遍历，每个节点和边最多访问一次，时间复杂度为 O(N + M)。
  • 检查是否可以移除：遍历 invocations，时间复杂度为 O(M)。
  • 总时间复杂度：O(N + M)。
• 空间复杂度：
  • 调用图 g：存储所有边，空间复杂度为 O(N + M)。
  • isSuspicious 数组：O(N)。
  • DFS 的递归栈或 BFS 的队列：最坏情况下为 O(N)。
  • 总空间复杂度：O(N + M)。

总结：

• 时间复杂度：O(N + M)。
• 空间复杂度：O(N + M)。

Go完整代码如下：

package main

import (
	"fmt"
)

func remainingMethods(n, k int, invocations [][]int) (ans []int) {
	g := make([][]int, n)
	for _, e := range invocations {
		g[e[0]] = append(g[e[0]], e[1])
	}

	// 标记所有可疑方法
	isSuspicious := make([]bool, n)
	var dfs func(int)
	dfs = func(x int) {
		isSuspicious[x] = true
		for _, y := range g[x] {
			if !isSuspicious[y] { // 避免无限递归
				dfs(y)
			}
		}
	}
	dfs(k)

	// 检查是否有【非可疑方法】->【可疑方法】的边
	for _, e := range invocations {
		if !isSuspicious[e[0]] && isSuspicious[e[1]] {
			// 无法移除可疑方法
			for i := range n {
				ans = append(ans, i)
			}
			return
		}
	}

	// 移除所有可疑方法
	for i, b := range isSuspicious {
		if !b {
			ans = append(ans, i)
		}
	}
	return
}

func main() {
	n := 4
	k := 1
	invocations := [][]int{{1, 2}, {0, 1}, {3, 2}}
	result := remainingMethods(n, k, invocations)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def remaining_methods(n: int, k: int, invocations: List[List[int]]) -> List[int]:
    # 构建邻接表，表示调用关系
    g = [[] for _ in range(n)]
    for a, b in invocations:
        g[a].append(b)

    # 标记所有可疑方法
    is_suspicious = [False] * n

    def dfs(x: int):
        is_suspicious[x] = True
        for y in g[x]:
            if not is_suspicious[y]:
                dfs(y)

    dfs(k)

    # 检查是否有非可疑方法调用了可疑方法
    for a, b in invocations:
        if not is_suspicious[a] and is_suspicious[b]:
            # 无法移除任何可疑方法，返回所有方法
            return list(range(n))

    # 移除所有可疑方法，返回剩余方法列表
    return [i for i, suspicious in enumerate(is_suspicious) if not suspicious]
if __name__ == "__main__":
    n = 4
    k = 1
    invocations = [[1, 2], [0, 1], [3, 2]]
    result = remaining_methods(n, k, invocations)
    print(result)  # 输出结果