Remove Methods From Project
Source: leetcode
Difficulty: Medium
Tags: depth-first-search, breadth-first-search, graph

You are maintaining a project that has `n` methods numbered from `0` to `n - 1`.


You are given two integers `n` and `k`, and a 2D integer array `invocations`, where `invocations[i] = [ai, bi]` indicates that method `ai` invokes method `bi`.


There is a known bug in method `k`. Method `k`, along with any method invoked by it, either **directly** or **indirectly**, are considered **suspicious** and we aim to remove them.


A group of methods can only be removed if no method **outside** the group invokes any methods **within** it.


Return an array containing all the remaining methods after removing all the **suspicious** methods. You may return the answer in *any order*. If it is not possible to remove **all** the suspicious methods, **none** should be removed.


 


**Example 1:**



**Input:** n \= 4, k \= 1, invocations \= \[\[1,2],\[0,1],\[3,2]]


**Output:** \[0,1,2,3]


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/07/18/graph-2.png)


Method 2 and method 1 are suspicious, but they are directly invoked by methods 3 and 0, which are not suspicious. We return all elements without removing anything.



**Example 2:**



**Input:** n \= 5, k \= 0, invocations \= \[\[1,2],\[0,2],\[0,1],\[3,4]]


**Output:** \[3,4]


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/07/18/graph-3.png)


Methods 0, 1, and 2 are suspicious and they are not directly invoked by any other method. We can remove them.



**Example 3:**



**Input:** n \= 3, k \= 2, invocations \= \[\[1,2],\[0,1],\[2,0]]


**Output:** \[]


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/07/20/graph.png)


All methods are suspicious. We can remove them.



 


**Constraints:**


- `1 <= n <= 105`
- `0 <= k <= n - 1`
- `0 <= invocations.length <= 2 * 105`
- `invocations[i] == [ai, bi]`
- `0 <= ai, bi <= n - 1`
- `ai != bi`
- `invocations[i] != invocations[j]`




C++ solution:
class Solution {
public:
    void dfs(vector<int> adj[], int node, vector<int> &vis){
        vis[node] = 1;
        for (int child: adj[node]){
            if (!vis[child]) dfs(adj,child,vis);
        }
    }

    vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
        vector<int> adj[n]; // adjancency list
        for (auto &x: invocations){
            adj[x[0]].emplace_back(x[1]);
        }

        // creating the visited array and calling the DFS
        vector<int> vis(n,0);
        dfs(adj,k,vis);

        // checking if any node is externally invoked
        bool c = false;
        for (int i = 0; i < n; i++){
            bool tmp = false;
            if (!vis[i]){ // external node
                for (int x: adj[i]){
                    if (vis[x]){
                        tmp = true;
                        break;
                    }
                }
                if (tmp){
                    c = true;
                    break;
                }
            }
        }

        // creating the answer array
        vector<int> ans;
        for (int i = 0; i < n; i++){
            if (vis[i]){
                if (c) ans.emplace_back(i);
            } else {
                ans.emplace_back(i);
            }
        }
        return ans;
    }
};

Go solution:
func remainingMethods(n int, k int, invocations [][]int) []int {
    // dfs and determine
    adj := map[int][]int{}
    for _,v := range(invocations) {
        adj[v[0]] = append(adj[v[0]], v[1])
    }
    within := map[int]bool{}
    res := []int{}
    stack := []int{k}
    for len(stack) > 0 {
        top := stack[len(stack) - 1]
        within[top] = true
        stack = stack[:len(stack) - 1]
        for _,v := range(adj[top]) {
            if !within[v] {
                stack = append(stack, v)
            }
        }
    }  
    for _,v  := range(invocations) {
        if !within[v[0]] && within[v[1]] {
            curr := []int{}
            for i := 0 ; i < n ; i ++ {
                curr = append(curr,  i)
            }
                        return curr
        }
    }
    for i := 0 ; i < n ; i ++ {
        if !within[i] {
        res = append(res,  i)

        }
    }
    return res 

}

Java solution:
class Solution {
    
    private void solveGraph(List<List<Integer>> adj, boolean[] vis, int k){
        vis[k]=true;
        
        Stack<Integer> stck = new Stack<>();
        stck.push(k);
        while(!stck.isEmpty()){
            int top = stck.pop();
            
            for(int ad:adj.get(top)){
                if(!vis[ad]){
                    vis[ad]=true;
                    stck.push(ad);
                }
            }
        }
    }
    
    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
        List<List<Integer>> adj = new ArrayList<>(n);
        for(int i=0; i<n; i++){
            adj.add(new ArrayList<>());
        }
        for(int[] invocation:invocations){
            adj.get(invocation[0]).add(invocation[1]);
        }
        
        boolean[] vis = new boolean[n];
        solveGraph(adj, vis, k);
        for(int i=0; i<n; i++){
            if(!vis[i]){
                for(int ad:adj.get(i)){
                    if(vis[ad]){
                        List<Integer> list = new ArrayList<>();
                        for(int i1=0; i1<n; i1++){
                            list.add(i1);
                        }
                        return list;
                    }
                }
            }
        }
        
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<n; i++){
            if(!vis[i]){
                list.add(i);
            }
        }
        return list;
    }
}

JavaScript solution:
var remainingMethods = function(n, k, invocations) {
    const adj = Array.from({ length: n }, () => []);
    for (const [a, b] of invocations) {
        adj[a].push(b);
    }

    const visited = new Set();
    const queue = [k];
    visited.add(k);
    let index = 0;
    while (index < queue.length) {
        const u = queue[index++];
        for (const v of adj[u]) {
            if (!visited.has(v)) {
                visited.add(v);
                queue.push(v);
            }
        }
    }

    let hasExternalCall = false;
    for (const [a, b] of invocations) {
        if (!visited.has(a) && visited.has(b)) {
            hasExternalCall = true;
            break;
        }
    }

    if (hasExternalCall) {
        return Array.from({ length: n }, (_, i) => i);
    } else {
        const result = [];
        for (let i = 0; i < n; i++) {
            if (!visited.has(i)) result.push(i);
        }
        return result;
    }
};

Python solution:
class Solution:
    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
        adj = {i: [] for i in range(n)}
        for src, dst in invocations:
            adj[src].append(dst)

        q = [k]
        visited = set([k])
        while q:
            suspicious = q.pop()
            for neighbor in adj[suspicious]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    q.append(neighbor)
                    
        ans = []
        for method in range(n):
            if method in visited: continue
            for neighbor in adj[method]:
                if neighbor in visited:
                    return list(range(n))
            ans.append(method)
        return ans

Ruby solution:
def remaining_methods(n, k, invocations)
  adj = Hash.new { |h, key| h[key] = [] }
  invocations.each { |ai, bi| adj[ai] << bi }

  visited = Array.new(n, false)
  queue = [k]
  visited[k] = true

  until queue.empty?
    current = queue.shift
    adj[current].each do |neighbor|
      unless visited[neighbor]
        visited[neighbor] = true
        queue << neighbor
      end
    end
  end

  can_remove = true
  invocations.each do |ai, bi|
    if visited[bi] && !visited[ai]
      can_remove = false
      break
    end
  end

  if can_remove
    (0...n).filter { |i| !visited[i] }
  else
    (0...n).to_a
  end
end