There are a total of n courses you have to take, labeled from0ton-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:
You may assume that there are no duplicate edges in the input prerequisites.
class Solution {
private ArrayList[] graph;
public boolean canFinish(int numCourses, int[][] prerequisites) {
graph = new ArrayList [numCourses];
// states: 0 = unknown, 1 = visiting, 2 = visited
int[] visit = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList < Integer > ();
}
for (int[] p: prerequisites) {
graph[p[0]].add(p[1]);
}
for (int i = 0; i < numCourses; i++) {
if (dfsCyclic(i, visit)) return false;
}
return true;
}
private boolean dfsCyclic(int cur, int[] v) {
if (v[cur] == 1) return true;
if (v[cur] == 2) return false;
v[cur] = 1;
for (int i = 0; i < graph[cur].size(); i++) {
if (dfsCyclic((int) graph[cur].get(i), v)) return true;
}
v[cur] = 2;
return false;
}
}
Topological Sort - OO Style - DFS (8ms 87.81% AC)
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Course[] courses = new Course[numCourses];
for (int i = 0; i < numCourses; i++) {
courses[i] = new Course();
}
for (int i = 0; i < prerequisites.length; i++) {
courses[prerequisites[i][0]].add(courses[prerequisites[i][1]]);
}
for (int i = 0; i < numCourses; i++) {
if (isCyclic(courses[i])) return false;
}
return true;
}
private boolean isCyclic(Course cur) {
if (cur.tested) return false;
if (cur.visited) return true;
cur.visited = true;
for (Course c: cur.pre) {
if (isCyclic(c)) {
return true;
}
}
cur.tested = true;
return false;
}
class Course {
boolean visited = false; // being visited
boolean tested = false; // tested if cyclic
List < Course > pre = new ArrayList < Course > ();
public void add(Course c) {
pre.add(c);
}
}
}
BFS
public class Solution {
/**
* @param numCourses a total of n courses
* @param prerequisites a list of prerequisite pairs
* @return true if can finish all courses or false
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
// Write your code here
List[] edges = new ArrayList[numCourses];
int[] degree = new int[numCourses];
for (int i = 0;i < numCourses; i++)
edges[i] = new ArrayList<Integer>();
for (int i = 0; i < prerequisites.length; i++) {
degree[prerequisites[i][0]] ++ ;
edges[prerequisites[i][1]].add(prerequisites[i][0]);
}
Queue queue = new LinkedList();
for(int i = 0; i < degree.length; i++){
if (degree[i] == 0) {
queue.add(i);
}
}
int count = 0;
while(!queue.isEmpty()){
int course = (int)queue.poll();
count ++;
int n = edges[course].size();
for(int i = 0; i < n; i++){
int pointer = (int)edges[course].get(i);
degree[pointer]--;
if (degree[pointer] == 0) {
queue.add(pointer);
}
}
}
return count == numCourses;
}
}