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?

For example:

2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]
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.

这是一道有关图的经典题，本质就是能否进行拓扑排序，拓扑排序必须是有向无环图，因此我们要判断每个顶点开始是否有环，如果有环就不能进行拓扑排序，如果没有就可以，返回false，这种方法是DFS实现。我们还可以用BFS方法来解决，用BFS时主要要维护一个入度为0的集合，我们用队列来实现。下面是代码实现：

DFS：

public class Solution {
    boolean[] isVisited;
    boolean[] onStack;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(prerequisites == null || prerequisites.length == 0) return true;
        List<Integer>[] graph = new List[numCourses];
        isVisited = new boolean[numCourses];
        onStack = new boolean[numCourses];
        for(int i = 0; i < prerequisites.length; i++) {
            int key = prerequisites[i][1];
            int value = prerequisites[i][0];
            if(graph[key] == null) graph[key] = new ArrayList<Integer>();
            graph[key].add(value);
        }
        for(int i = 0; i < numCourses; i++) {
            if(isVisited[i] == false && hasCycle(i, graph) == true) return false;
        }
        return true;
    }
    
    public boolean hasCycle(int v, List<Integer>[] graph) {
        boolean cycle = false;
        isVisited[v] = true;
        onStack[v] = true;
        if(graph[v] != null) {
            for(int i : graph[v]) {
                if(isVisited[i] != true) {
                    cycle = hasCycle(i, graph);
                    if(cycle == true)
                        break;
                } else if(onStack[i] == true) {
                    cycle = true;
                    break;
                }
            }
        }
        onStack[v] = false;
        return cycle;
    }
}

BFS：

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
       if(prerequisites == null || prerequisites.length == 0) return true;
       int[] degree = new int[numCourses];
       List<Integer>[] graph = new List[numCourses];
       Queue<Integer> qSet = new LinkedList<Integer>();
       int edges = prerequisites.length;
       for(int i = 0; i < prerequisites.length; i++) {
           degree[prerequisites[i][0]] ++;
           int key = prerequisites[i][1];
           int value = prerequisites[i][0];
           if(graph[key] == null) graph[key] = new ArrayList<Integer>();
           graph[key].add(value);
       }
       for(int i = 0; i < degree.length; i++) {
           if(degree[i] == 0)
                qSet.offer(i);
       }
       while(!qSet.isEmpty()) {
           int tem = qSet.poll();
           if(graph[tem] != null) {
               for(int v : graph[tem]) {
                   edges --;
                   if(--degree[v] == 0)
                        qSet.offer(v);
               }
           }
       }
       if(edges != 0) return false;
       return true;
    }
}