Medium

题目描述

你正在维护一个有 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 直接调用。我们返回所有元素而不移除任何内容。

示例 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]

解题思路

解题思路

这道题可以分为两个步骤来解决：

  1. 找到所有可疑方法：从方法 k 开始进行 DFS/BFS，找到所有被 k 直接或间接调用的方法。这些方法都是可疑的。

  2. 检查是否能移除可疑方法：检查是否有非可疑的方法调用了可疑方法。如果存在这样的调用，则不能移除任何可疑方法；否则可以移除所有可疑方法。

具体算法步骤：

  • 构建调用图（邻接表）
  • 从方法 k 开始 DFS，标记所有可疑方法
  • 遍历所有调用关系，检查是否有非可疑方法调用可疑方法
  • 如果没有外部调用，返回所有非可疑方法；否则返回所有方法

时间复杂度为 O(n + m)，其中 m 是调用关系的数量。空间复杂度为 O(n + m)。

代码实现

class Solution {
public:
    vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
        // 构建调用图
        vector<vector<int>> graph(n);
        for (auto& inv : invocations) {
            graph[inv[0]].push_back(inv[1]);
        }
        
        // 找到所有可疑方法
        vector<bool> suspicious(n, false);
        dfs(graph, k, suspicious);
        
        // 检查是否有非可疑方法调用可疑方法
        bool canRemove = true;
        for (auto& inv : invocations) {
            int from = inv[0], to = inv[1];
            if (!suspicious[from] && suspicious[to]) {
                canRemove = false;
                break;
            }
        }
        
        // 返回结果
        vector<int> result;
        if (canRemove) {
            // 返回非可疑方法
            for (int i = 0; i < n; i++) {
                if (!suspicious[i]) {
                    result.push_back(i);
                }
            }
        } else {
            // 返回所有方法
            for (int i = 0; i < n; i++) {
                result.push_back(i);
            }
        }
        
        return result;
    }
    
private:
    void dfs(vector<vector<int>>& graph, int node, vector<bool>& suspicious) {
        if (suspicious[node]) return;
        suspicious[node] = true;
        for (int next : graph[node]) {
            dfs(graph, next, suspicious);
        }
    }
};

class Solution:
    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
        # 构建调用图
        graph = [[] for _ in range(n)]
        for a, b in invocations:
            graph[a].append(b)
        
        # 找到所有可疑方法
        suspicious = [False] * n
        self.dfs(graph, k, suspicious)
        
        # 检查是否有非可疑方法调用可疑方法
        can_remove = True
        for a, b in invocations:
            if not suspicious[a] and suspicious[b]:
                can_remove = False
                break
        
        # 返回结果
        if can_remove:
            # 返回非可疑方法
            return [i for i in range(n) if not suspicious[i]]
        else:
            # 返回所有方法
            return list(range(n))
    
    def dfs(self, graph, node, suspicious):
        if suspicious[node]:
            return
        suspicious[node] = True
        for next_node in graph[node]:
            self.dfs(graph, next_node, suspicious)

public class Solution {
    public IList<int> RemainingMethods(int n, int k, int[][] invocations) {
        // 构建调用图
        var graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var inv in invocations) {
            graph[inv[0]].Add(inv[1]);
        }
        
        // 找到所有可疑方法
        var suspicious = new bool[n];
        Dfs(graph, k, suspicious);
        
        // 检查是否有非可疑方法调用可疑方法
        bool canRemove = true;
        foreach (var inv in invocations) {
            int from = inv[0], to = inv[1];
            if (!suspicious[from] && suspicious[to]) {
                canRemove = false;
                break;
            }
        }
        
        // 返回结果
        var result = new List<int>();
        if (canRemove) {
            // 返回非可疑方法
            for (int i = 0; i < n; i++) {
                if (!suspicious[i]) {
                    result.Add(i);
                }
            }
        } else {
            // 返回所有方法
            for (int i = 0; i < n; i++) {
                result.Add(i);
            }
        }
        
        return result;
    }
    
    private void Dfs(List<int>[] graph, int node, bool[] suspicious) {
        if (suspicious[node]) return;
        suspicious[node] = true;
        foreach (int next in graph[node]) {
            Dfs(graph, next, suspicious);
        }
    }
}

var remainingMethods = function(n, k, invocations) {
    // 构建调用图
    const graph = Array(n).fill(null).map(() => []);
    for (const [a, b] of invocations) {
        graph[a].push(b);
    }
    
    // 找到所有可疑方法
    const suspicious = new Array(n).fill(false);
    
    const dfs = (node) => {
        if (suspicious[node]) return;
        suspicious[node] = true;
        for (const next of graph[node]) {
            dfs(next);
        }
    };
    
    dfs(k);
    
    // 检查是否有非可疑方法调用可疑方法
    let canRemove = true;
    for (const [a, b] of invocations) {
        if (!suspicious[a] && suspicious[b]) {
            canRemove = false;
            break;
        }
    }
    
    // 返回结果
    const result = [];
    if (canRemove) {
        // 返回非可疑方法
        for (let i = 0; i < n; i++) {
            if (!suspicious[i]) {
                result.push(i);
            }
        }
    } else {
        // 返回所有方法
        for (let i = 0; i < n; i++) {
            result.push(i);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)其中 n 是方法数量，m 是调用关系数量。需要遍历图进行 DFS，然后检查所有调用关系
空间复杂度O(n + m)需要存储图的邻接表和标记数组