Course Schedule

LeetCode Q 207 - Course Schedule

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?

Example 1:
Input: 2, [[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: 2, [[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.

Note:

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is .
• You may assume that there are no duplicate edges in the input prerequisites.

Solution

Solution 1 : BFS

Code:

public boolean canFinish(int numCourses, int[][] reqs) {
	if (numCourses <= 0 || reqs == null || reqs.length == 0) 
		return true;

	// build the graph and order array
	Map<Integer, Set<Integer>> graph = new HashMap<>();
	int[] order = new int[numCourses];

	for (int i = 0; i < numCourses; i++)
		graph.put(i, new HashSet<>());
	for (int[] req: reqs) {
		graph.get(req[1]).add(req[0]);
		order[req[0]]++;
	}

	Queue<Integer> que = new LinkedList<>();
	for (int i = 0; i < numCourses; i++) {
		if (order[i] == 0) que.offer(numCourses);
	}

	int count = 0;
	while (!que.isEmpty()) {
		int curr = que.poll();
		count++;
		for (int next: graph.get(curr)) {
			order[next]--;
			if (order[next] == 0)	
				que.offer(next);
		}
	}
	
	return count == numCourses;
}

Solution 2 : DFS

Tip:
Use an int[] status to represent the status of the current node.
It has 3 potential values, i.e.
0: unvisited; 1: visiting; 2: visited.

Code:

public boolean canFinish(int numCourses, int[][] reqs) {
	if (numCourses <= 0 || reqs == null || reqs.length == 0) 
		return true;

	// build the graph 
	Map<Integer, Set<Integer>> graph = new HashMap<>();
	for (int i = 0; i < numCourses; i++)
		graph.put(i, new HashSet<>());
	for (int[] req: reqs) 
		graph.get(req[1]).add(req[0]);

	int[] status = new int[numCourses];

	for (int i = 0; i < numCourses; i++) {
		if (status[i] == 2) continue;
		if (hasCycle(graph, i, status))
			return false;
	}

	return true;
}

private boolean hasCycle(Map<Integer, Set<Integer>> graph, int course, int[] status) {
	if (status[course] == 1) return true;

	status[course] = 1;
	for (int next: graph.get(course)) {
		if (status[i] == 2) continue;
		if (hasCycle(graph, next, status))
			return true;
	}

	status[course] = 2;

	return false;
}