Leetcode 3310. Remove Methods From Project

• Leetcode 3310. Remove Methods From Project
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3310. Remove Methods From Project

1. 解题思路

这一题我的做法比较暴力，就是先使用dsu将所有的method进行分组，然后找到和目标的method相关的所有的节点，看看其是否上游依赖于损坏的节点即可。

关于分组，我们使用一个dsu算法即可快速搞定，而关于后者，我们使用一个有向图的遍历即可完成。

而关于dsu算法的内容，网上有很多相关的内容，我自己也写过一个博客作为备忘录（经典算法：并查集（DSU）结构简介），有兴趣的读者可以移步去看看，这里就不过多展开了。

2. 代码实现

给出python实现如下：

class DSU:def __init__(self, n):self.root = [i for i in range(n)]def find(self, k):if self.root[k] != k:self.root[k] = self.find(self.root[k])return self.root[k]def union(self, u, v):x = self.find(u)y = self.find(v)if x != y:self.root[y] = xreturnclass Solution:def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:dsu = DSU(n)for u, v in invocations:dsu.union(u, v)u = dsu.find(k)remain = [i for i in range(n) if dsu.find(i) != u]remove = [i for i in range(n) if dsu.find(i) == u]graph = defaultdict(list)for u, v in invocations:graph[u].append(v)seen = {k}q = [k]while q != []:u = q.pop(0)for v in graph[u]:if v not in seen:seen.add(v)q.append(v)return remain if len(remove) == len(seen) else [i for i in range(n)]

提交代码评测得到：耗时3352ms，占用内存124.7MB。