Amazon

Apple

Bytedance

Microsoft

Oracle

2020-05-29

## 207. Course Schedule

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses-1`.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: `[0,1]`

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

### Question:

#### Example 1:

``````Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
``````

#### Example 2:

``````Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
``````

Constraints:

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
• You may assume that there are no duplicate edges in the input prerequisites.
• `1 <= numCourses <= 10^5`

### Solution:

Store each course with its in node number and outnode list. Using BFS topological sort to find if we can visit all the nodes.

Time: O(V+E)
Space: O(V+E)

``````class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0) return true;
HashMap<Integer, List<Integer>> map = new HashMap<>();
int[] counter = new int[numCourses];
Queue<Integer> que = new LinkedList<>();
int result = 0;

for (int[] i : prerequisites) {
int from = i;
int to = i;
List<Integer> curr = map.getOrDefault(from, new ArrayList<>());
map.put(from, curr);
counter[to]++;
}

for (int i = 0; i < numCourses; i++) {
if (counter[i] == 0) {
}
}

while (!que.isEmpty()) {
int curr = que.poll();
result++;
if (map.containsKey(curr)) {
for (int i : map.get(curr)) {
counter[i]--;
if (counter[i] == 0) {