LeetCode 3310. 移除可疑的方法

LeetCode 3310. 移除可疑的方法
   你正在维护一个项目，该项目有 n 个方法，编号从 0 到 n - 1。
给你两个整数 n 和 k，以及一个二维整数数组 invocations，其中 invocations = [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 == [ai, bi]
0 <= ai, bi <= n - 1
ai != bi
invocations != invocations[j]
  图、图的遍历

1. class Node:
2.     def __init__(self, val):
3.         self.val = val
4.         self.next = []
5.         self.prev = []
8. class Solution:
9.     def remainingMethods(
10.         self, n: int, k: int, invocations: List[List[int]]
11.     ) -> List[int]:
12.         if not invocations:
13.             return list(set(range(n)) - set([k]))
15.         # 建图
16.         method_mapping = {}
17.         for a, b in invocations:
18.             # a -> b
19.             if a not in method_mapping:
20.                 method_mapping[a] = Node(a)
21.             if b not in method_mapping:
22.                 method_mapping[b] = Node(b)
23.             node = method_mapping[a]
24.             node.next.append(method_mapping[b])
25.         for i in range(n):
26.             if i not in method_mapping:
27.                 method_mapping[i] = Node(i)
29.         # 查出所有可疑方法
30.         bad_method_set = set()
31.         q = deque([method_mapping[k]])
32.         while q:
33.             node = q.popleft()
34.             bad_method_set.add(node.val)
35.             for i in node.next:
36.                 if i.val not in bad_method_set:
37.                     q.append(i)
39.         # 验证是否刚好能移除可疑方法
40.         flag = True
41.         for a, b in invocations:
42.             if a in bad_method_set and b not in bad_method_set:
43.                 flag = False
44.                 break
45.             elif a not in bad_method_set and b in bad_method_set:
46.                 flag = False
47.                 break
49.         l = bad_method_set if flag else set()
51.         return list(set(range(n)) - l)

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。