A school offers courses numbered 0, 1, 2, ..., n-1. You're given n
.
You're also given an array prerequisites
that has pairs of courses [a,b], telling you that students must take course a before taking course b.
You're also given course numbers A
and B
. Return whether students must take A
before B
.
Example:
Explanation: Students must take course 0 before course 2, even though [0,2] isn't explicitly stated as a prerequisite. This is because course 2 requires taking 1 and 1 requires taking 0.
To understand this problem better, we can draw things visually using a graph. We'll draw an arrow from each course to the courses that must come first. Here's what prerequisites=[[0,1],[1,2],[1,3]]
looks like:
This graph makes it clear that 0 needs to come before all the other courses. In general, if we want to check if A is a prerequisite of B, we can just start at B and search along this graph to see if we ever reach A. For example, if we want to check if 0 is a prerequisite of 2, we'd start at the 2 and check if we ever reach 0 (this does happen, so 0 is indeed a prerequisite of 2).
A DFS would be easy here and would work fine, but it might take a while if it goes down the wrong branch:
So we'll search the graph using a BFS instead, to make sure we don't waste time going too deep down the wrong path.
0. Problem
We'll create the graph of the prerequisites in an "adjacency matrix", where we store the neighbors of each node in an array. You can see the Cheat Sheet for more details about storing graphs. Here's how we build the adjacency matrix:
3. Code
To code this up, we'll do a BFS starting at course B and seeing if we can get to course A. To do a BFS, you should use a queue to add/remove elements, and you should keep track of what you've visited to make sure you never enter an infinite loop. Here's the code:
Time Complexity O(numCourses+E). We create the adjacency matrix which takes O(numCourses+E) time. Then we iterate through the O(E) edges.
Space Complexity O(numCourses+E). Every course gets at least one entry in the adjacency matrix, and so does every edge.