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?
https://leetcode.com/problems/course-schedule/
Java:
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses == 0 || prerequisites.length == 0 || prerequisites[0].length == 0) {
return true;
}
Map<Integer, Set<Integer>> graph = new HashMap<>();
int[] indegrees = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph.put(i, new HashSet<>());
}
// Build the graph
for (int i = 0; i < prerequisites.length; i++) {
graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
indegrees[prerequisites[i][0]]++;
}
// Add nodes with 0 indegree to the queue.
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegrees[i] == 0) {
queue.add(i);
}
}
while (!queue.isEmpty()) {
int curt = queue.remove();
for (Integer i : graph.get(curt)) {
indegrees[i]--;
if (indegrees[i] == 0) {
queue.add(i);
}
}
}
for (int i = 0; i < numCourses; i++) {
if (indegrees[i] > 0) {
return false;
}
}
return true;
}
}