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:

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

一刷
题解：用BST实现Topological sort
先把in-degree为0（没有需要先修的课程）的点（course)入队列，寻找它的下一个要修的课程，如果修了之后in-degree为1， 继续入队列。如果队列为空的时候pull的次数为course，那么可以全部修完。

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] matrix = new int[numCourses][numCourses];
        int[] indegree = new int[numCourses]; //if select this one, how many courses should be selected
        
        for(int i=0; i<prerequisites.length; i++){
            int ready = prerequisites[i][0];
            int pre = prerequisites[i][1];
            if(matrix[pre][ready] == 0){
                indegree[ready]++;//in case there is duplicate
            }
            matrix[pre][ready] = 1;
        }
        
        int count = 0;
        Queue<Integer> queue = new LinkedList();
        for(int i=0; i<numCourses; i++){
            if(indegree[i] == 0) queue.offer(i);
        }
        while(!queue.isEmpty()){
            int course = queue.poll();//no pre
            count++;
            for(int i=0; i<numCourses; i++){
                if(matrix[course][i]!=0){
                    if(--indegree[i] == 0) queue.offer(i);
                }
            }
        }
        return count == numCourses;
    }
}

二刷
dfs

• 暴力解法：DFS + Backtracking，寻找“所有从当前节点的” path，如果试图访问 visited 则有环；缺点是，同一个点会被探索多次，而且要从所有点作为起点保证算法正确性，时间复杂度非常高
• 最优解法是 CLRS 上用三种状态表示每个节点：
  "0" 还未访问过;
  "1" 代表正在访问；
  "2" 代表已经访问过；
  DFS 开始时把当前节点设为 "1";
  在从任意节点出发的时候，如果我们试图访问一个状态为 "1" 的节点，都说明图上有环。但是允许访问一个为"2"的点，这样表示接入之前的路径。 比如a->b->c, b->c为2，a可以再次访问2
  当前节点的 DFS 结束时，设为 "2";
  在找环上，DFS 比起 BFS 最大的优点是"对路径有记忆"，DFS 记得来时的路径和导致环的位置，BFS 却不行。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        for(int i=0; i<numCourses; i++) graph[i] = new ArrayList<Integer>();
        boolean[] visited = new boolean[numCourses];
        
        for(int[] pair : prerequisites){
            graph[pair[0]].add(pair[1]);
        }
        
        for(int i=0; i<numCourses; i++){
            if(!dfs(graph, visited, i)) return false;
        }
        return true;
    }
    
    private boolean dfs(ArrayList[] graph, boolean[] visited, int course){
        if(visited[course]) return false;
        visited[course] = true;
        for(int i=0; i<graph.get(course).size(); i++){
            if(!dfs(graph, visited, (int)graph.get(course).get(i))) return false;
        }
        visited[course] = false;
        return true;
    }
}