8,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1b:I[4544,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1d:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:T5bd,

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.

Video explanation

Here is the video explaining this method in detail. Please check it out:

1c:T9b2,

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 n

Related Tags