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] = x
        return


class 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。