Skip to content

1462. Course Schedule IV 👍

Approach 1: DFS

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 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
class Solution {
 public:
  vector<bool> checkIfPrerequisite(int numCourses,
                                   vector<vector<int>>& prerequisites,
                                   vector<vector<int>>& queries) {
    vector<bool> ans;
    vector<vector<int>> graph(numCourses);
    // isPrerequisite[i][j] := true if course i is a prerequisite of course j
    vector<vector<bool>> isPrerequisite(numCourses, vector<bool>(numCourses));

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

    // DFS from every course.
    for (int i = 0; i < numCourses; ++i)
      dfs(graph, i, isPrerequisite[i]);

    for (const vector<int>& query : queries) {
      const int u = query[0];
      const int v = query[1];
      ans.push_back(isPrerequisite[u][v]);
    }

    return ans;
  }

  void dfs(const vector<vector<int>>& graph, int u, vector<bool>& used) {
    for (const int v : graph[u]) {
      if (used[v])
        continue;
      used[v] = true;
      dfs(graph, v, used);
    }
  }
};

 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
class Solution {
  public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
    List<Boolean> ans = new ArrayList<>();
    List<Integer>[] graph = new List[numCourses];

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

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

    // isPrerequisite[i][j] := true if course i is a prerequisite of course j
    boolean[][] isPrerequisite = new boolean[numCourses][numCourses];

    // DFS from every course.
    for (int i = 0; i < numCourses; ++i)
      dfs(graph, i, isPrerequisite[i]);

    for (int[] query : queries) {
      final int u = query[0];
      final int v = query[1];
      ans.add(isPrerequisite[u][v]);
    }

    return ans;
  }

  public void dfs(List<Integer>[] graph, int u, boolean[] used) {
    for (final int v : graph[u]) {
      if (used[v])
        continue;
      used[v] = true;
      dfs(graph, v, used);
    }
  }
}

 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
class Solution:
  def checkIfPrerequisite(
      self,
      numCourses: int,
      prerequisites: list[list[int]],
      queries: list[list[int]],
  ) -> list[bool]:
    graph = [[] for _ in range(numCourses)]
    # isPrerequisite[i][j] := True if course i is a prerequisite of course j.
    isPrerequisite = [[False] * numCourses for _ in range(numCourses)]

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

    # DFS from every course.
    for i in range(numCourses):
      self._dfs(graph, i, isPrerequisite[i])

    return [isPrerequisite[u][v] for u, v in queries]

  def _dfs(self, graph: list[list[int]], u: int, used: list[bool]) -> None:
    for v in graph[u]:
      if used[v]:
        continue
      used[v] = True
      self._dfs(graph, v, used)

Approach 2: Floyd-Warshall

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 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
class Solution {
 public:
  vector<bool> checkIfPrerequisite(int numCourses,
                                   vector<vector<int>>& prerequisites,
                                   vector<vector<int>>& queries) {
    vector<bool> ans;
    // isPrerequisite[i][j] := true if course i is a prerequisite of course j
    vector<vector<bool>> isPrerequisite(numCourses, vector<bool>(numCourses));

    for (const vector<int>& prerequisite : prerequisites) {
      const int u = prerequisite[0];
      const int v = prerequisite[1];
      isPrerequisite[u][v] = true;
    }

    for (int k = 0; k < numCourses; ++k)
      for (int i = 0; i < numCourses; ++i)
        for (int j = 0; j < numCourses; ++j)
          isPrerequisite[i][j] = isPrerequisite[i][j] ||
                                 (isPrerequisite[i][k] && isPrerequisite[k][j]);

    for (const vector<int>& query : queries) {
      const int u = query[0];
      const int v = query[1];
      ans.push_back(isPrerequisite[u][v]);
    }

    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
class Solution {
  public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
    List<Boolean> ans = new ArrayList<>();
    // isPrerequisite[i][j] := true if course i is a prerequisite of course j
    boolean[][] isPrerequisite = new boolean[numCourses][numCourses];

    for (int[] prerequisite : prerequisites) {
      final int u = prerequisite[0];
      final int v = prerequisite[1];
      isPrerequisite[u][v] = true;
    }

    for (int k = 0; k < numCourses; ++k)
      for (int i = 0; i < numCourses; ++i)
        for (int j = 0; j < numCourses; ++j)
          isPrerequisite[i][j] =
              isPrerequisite[i][j] || (isPrerequisite[i][k] && isPrerequisite[k][j]);

    for (int[] query : queries) {
      final int u = query[0];
      final int v = query[1];
      ans.add(isPrerequisite[u][v]);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def checkIfPrerequisite(
      self,
      numCourses: int,
      prerequisites: list[list[int]],
      queries: list[list[int]],
  ) -> list[bool]:
    # isPrerequisite[i][j] := True if course i is a prerequisite of course j.
    isPrerequisite = [[False] * numCourses for _ in range(numCourses)]

    for u, v in prerequisites:
      isPrerequisite[u][v] = True

    for k in range(numCourses):
      for i in range(numCourses):
        for j in range(numCourses):
          isPrerequisite[i][j] = (isPrerequisite[i][j] or (
              isPrerequisite[i][k] and isPrerequisite[k][j]))

    return [isPrerequisite[u][v] for u, v in queries]