Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Examples

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.

Solution

This problem can be converted to finding if a graph contains a cycle.

Method 1 - BFS

This solution uses breath-first search and it is easy to understand.

public boolean canFinish(int numCourses, int[][] prerequisites) {
	if (prerequisites == null) {
		throw new IllegalArgumentException("illegal prerequisites array");
	}

	int len = prerequisites.length;

	if (numCourses == 0 || len == 0) {
		return true;
	}

	// counter for number of prerequisites
	int[] pCounter = new int[numCourses];
	for (int i = 0; i<len; i++) {
		pCounter[prerequisites[i][0]]++;
	}

	//store courses that have no prerequisites
	LinkedList<Integer> queue = new LinkedList<Integer> ();
	for (int i = 0; i<numCourses; i++) {
		if (pCounter[i] == 0) {
			queue.add(i);
		}
	}

	// number of courses that have no prerequisites
	int numNoPre = queue.size();

	while (!queue.isEmpty()) {
		int top = queue.remove();
		for (int i = 0; i<len; i++) {
			// if a course's prerequisite can be satisfied by a course in queue
			if (prerequisites[i][1] == top) {
				pCounter[prerequisites[i][0]]--;
				if (pCounter[prerequisites[i][0]] == 0) {
					numNoPre++;
					queue.add(prerequisites[i][0]);
				}
			}
		}
	}

	return numNoPre == numCourses;
}

Method 2 - DFS

Thsi problem is very close to Topological Sorting.

public boolean canFinish(int numCourses, int[][] prerequisites) {
	if (prerequisites == null) {
		throw new IllegalArgumentException("illegal prerequisites array");
	}

	int len = prerequisites.length;

	if (numCourses == 0 || len == 0) {
		return true;
	}

	//track visited courses
	int[] visit = new int[numCourses];

	// use the map to store what courses depend on a course
	HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>> ();
	for (int[] a: prerequisites) {
		map.putIfAbsent(a[1], new ArrayList<Integer>());
		map.get(a[1]).add(a[0]);
	}

	for (int i = 0; i<numCourses; i++) {
		if (!canFinishDFS(map, visit, i))
			return false;
	}

	return true;
}

private boolean canFinishDFS(Map<Integer, List<Integer>> map, int[] visit, int i) {
	if (visit[i] == -1)
		return false;
	if (visit[i] == 1)
		return true;

	visit[i] = -1;
	if (map.containsKey(i)) {
		for (int j: map.get(i)) {
			if (!canFinishDFS(map, visit, j))
				return false;
		}
	}

	visit[i] = 1;

	return true;
}

Topological Sort Video from Coursera.