There are a total ofncourses 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 prerequisitepairs, 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.

Solution 1: BFS + topological sort.

hashmap用来建图：{起点，{终点}}.

hashmap2用来统计每个终点的入度 （小心有重复的边，所以hashmap的终点集用hashset）.

queue和hashset加入入度为0的顶点，每次queue弹出一个顶点，要把它的终点集入度减1.

最后看看是不是所有顶点都加入hashset，若不是则说明有环

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(prerequisites == null || prerequisites.length < 2 || prerequisites[0] == null || prerequisites[0].length < 2 || numCourses < 2){
            return true;
        }
        HashMap<Integer, HashSet<Integer>> hashmap = new HashMap<Integer, HashSet<Integer>>();
        HashMap<Integer, Integer> hashmap2 = new HashMap<Integer, Integer>();
        HashSet<Integer> hashset = new HashSet<Integer>();
        Queue<Integer> queue = new LinkedList<Integer>();
        int m = prerequisites.length;
        //建图
        for(int i = 0; i < m; i++){
            int node = prerequisites[i][0];
            int neighbour = prerequisites[i][1];
            if(hashmap.containsKey(node)){
                hashmap.get(node).add(neighbour);
            } else{
                HashSet<Integer> set = new HashSet<Integer>();
                set.add(neighbour);
                hashmap.put(node, set);
            }
        }
        //统计入度
        for(HashSet<Integer> set : hashmap.values()){
            for(Integer neighbour : set){
                hashmap2.put(neighbour, hashmap2.getOrDefault(neighbour, 0) + 1);
            }
        }
        //把入度为0的加入set和queue
        for(int i = 0; i < m; i++){
            int node = prerequisites[i][0];
            if(!hashmap2.containsKey(node)){
                queue.offer(node);
                hashset.add(node);
            }
        }
        while(!queue.isEmpty()){
            int node = queue.poll();
            if(!hashmap.containsKey(node)){
                continue;
            }
            for(Integer neighbour : hashmap.get(node)){
                if(hashset.contains(neighbour)){
                    continue;
                }
                int indegree = hashmap2.get(neighbour) - 1;
                hashmap2.put(neighbour, indegree);
                if(indegree == 0){
                    queue.offer(neighbour);
                    hashset.add(neighbour);
                }
            }
        }
        for(int i = 0; i < m; i++){
            int node = prerequisites[i][0];
            if(!hashset.contains(node)){
                return false;
            }
        }
        return true;
    }

better:

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses]; // i -> j
    int[] indegree = new int[numCourses];

    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]++; //duplicate case
        matrix[pre][ready] = 1;
    }

    int count = 0;
    Queue<Integer> queue = new LinkedList();
    for (int i=0; i<indegree.length; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
    return count == numCourses;
}

Solution 2: DFS. the solution basically starts at every node in the graph which corresponds to a course and traverses all the courses (nodes) that can be taken subsequently. If we ever encounter the a course we have already visited , then we know there is a cycle. Note that in the solution , as the recursion unwinds all the visited status is set to false. Hence every time DFS is started in the can finish function , the visted boolean array is guaranteed to be all false.

public boolean canFinish(int numCourses, int[][] prerequisites) {
    if(numCourses == 0 || prerequisites == null || prerequisites.length == 0) return true; //??

    // create the array lists to represent the courses
    List<List<Integer>> courses = new ArrayList<List<Integer>>(numCourses);
    for(int i=0; i<numCourses; i++) {
        courses.add(new ArrayList<Integer>());
    }

    // create the dependency graph
    for(int i=0; i<prerequisites.length; i++) {
        courses.get(prerequisites[i][1]).add(prerequisites[i][0]);
    }

    int[] visited = new int[numCourses]; 

    // dfs visit each course
    for(int i=0; i<numCourses; i++) {
           if (!dfs(i,courses, visited)) return false; 
    }

    return true;
}

private boolean dfs(int course, List<List<Integer>> courses, int[] visited) {

    visited[course] = 1; // mark it being visited

    List<Integer> eligibleCourses = courses.get(course); // get its children

    // dfs its children
    for(int i=0; i<eligibleCourses.size(); i++) {
        int eligibleCourse = eligibleCourses.get(i).intValue();

        if(visited[eligibleCourse] == 1) return false; // has been visited while visiting its children - cycle !!!!
        if(visited[eligibleCourse]  == 0) { // not visited
           if (!dfs(eligibleCourse,courses, visited)) return false; 
        }

    }

    visited[course] = 2; // mark it done visiting
    return true;

}