There are a total of *n* courses you have to take, labeled from `0`

to `n - 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?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

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.

**Note:**

- 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.

click to show more hints.

**Hints:**
- This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
- Topological Sort via DFS – A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
- Topological sort could also be done via BFS.

public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, Set<Integer>> inDegree = new HashMap<>();
Map<Integer, Set<Integer>> outDegree = new HashMap<>();
Set<Integer> set = new HashSet<>();
// Init courses
for (int i = 0; i < numCourses; i++) {
inDegree.put(i, new HashSet<>());
outDegree.put(i, new HashSet<>());
set.add(i);
}
// Parse course prerequisites
for (int i = 0; i < prerequisites.length; i++) {
int current = prerequisites[i][0];
int pre = prerequisites[i][1];
inDegree.get(current).add(pre);
outDegree.get(pre).add(current);
}
Queue<Integer> queue = new LinkedList<>();
for (Integer course : set) {
if (inDegree.get(course).size() == 0) {
queue.add(course);
}
}
int index = 0;
int[] result = new int[set.size()];
while (!queue.isEmpty()) {
Integer course = queue.poll();
result[index++] = course;
for (Integer next : outDegree.get(course)) {
inDegree.get(next).remove(course);
if (inDegree.get(next).size() == 0) {
queue.offer(next);
}
}
}
if (index != set.size()) {
return false;
} else {
return true;
}
}
}

### Like this:

Like Loading...

## Leave a Reply