Skip to content

3310. Remove Methods From Project

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
 public:
  vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
    vector<int> ans;
    vector<vector<int>> graph(n);

    for (const vector<int>& invocation : invocations) {
      const int u = invocation[0];
      const int v = invocation[1];
      graph[u].push_back(v);
    }

    queue<int> q{{k}};
    vector<bool> seen(n);
    seen[k] = true;

    while (!q.empty())
      for (int sz = q.size(); sz > 0; --sz) {
        const int u = q.front();
        q.pop();
        for (const int v : graph[u])
          if (!seen[v]) {
            q.push(v);
            seen[v] = true;
          }
      }

    for (int u = 0; u < n; ++u) {
      if (seen[u])
        continue;
      for (const int v : graph[u])
        if (seen[v]) {
          ans.resize(n);
          iota(ans.begin(), ans.end(), 0);
          return ans;
        }
      ans.push_back(u);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
  public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
    List<Integer> ans = new ArrayList<>();
    List<Integer>[] graph = new List[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] invocation : invocations) {
      final int u = invocation[0];
      final int v = invocation[1];
      graph[u].add(v);
    }

    Queue<Integer> q = new ArrayDeque<>(List.of(k));
    boolean[] seen = new boolean[n];
    seen[k] = true;

    while (!q.isEmpty())
      for (int sz = q.size(); sz > 0; --sz)
        for (final int v : graph[q.poll()])
          if (!seen[v]) {
            q.offer(v);
            seen[v] = true;
          }

    for (int u = 0; u < n; ++u) {
      if (seen[u])
        continue;
      for (final int v : graph[u])
        if (seen[v]) {
          ans = new ArrayList<>(n);
          for (int i = 0; i < n; ++i)
            ans.add(i);
          return ans;
        }
      ans.add(u);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
  def remainingMethods(
      self,
      n: int,
      k: int,
      invocations: list[list[int]]
  ) -> list[int]:
    ans = []
    graph = [[] for _ in range(n)]

    for u, v in invocations:
      graph[u].append(v)

    q = collections.deque([k])
    seen = {k}

    while q:
      for _ in range(len(q)):
        for v in graph[q.popleft()]:
          if v not in seen:
            q.append(v)
            seen.add(v)

    for u in range(n):
      if u in seen:
        continue
      for v in graph[u]:
        if v in seen:
          return list(range(n))
      ans.append(u)

    return ans