Question:

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. Read more about how a graph is represented.

click to show more hints.

Hints:
This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.

Thinking:

We can search it from a arbitary node, can search by DFS. If there is a cycle, we will meet the visited nodes once DFS. So we need a array to hold the visited record. By the way, if we want a topological sort, we can hold a current value which is number of nodes initially and decrese one only when meet a sink node.

For BFS, we can find the nodes whose indegree or outdegree is zero, and search from them. If there is a cycle, the number of nodes searched will less than the exact number because in a cycle no nodes’ indegree or outdegree is zero.

Solution:

DFS:

public boolean canFinish(int numCourses, int[][] prerequisites) {
    if (numCourses <= 1)
        return true;
    ArrayList<HashSet<Integer>> edges = new ArrayList<HashSet<Integer>>(numCourses);
    boolean[] visited = new boolean[numCourses];

    for (int i = 0; i < numCourses; i++)
        edges.add(new HashSet<Integer>());

    for (int[] pre: prerequisites){
        edges.get(pre[0]).add(pre[1]);
    }

    for (int i = 0; i < numCourses; i++){
        if (edges.get(i).size() != 0)
            if (!dfs(edges, i, visited))
                return false;
    }

    return true;
}

private boolean dfs(ArrayList<HashSet<Integer>> edges, int i, boolean[] visited){
    if (visited[i] == true)
        return false;
    visited[i] = true;
    while (edges.get(i).size() != 0){
        int j = edges.get(i).iterator().next();

        if (!dfs(edges, j, visited))
            return false;

        edges.get(i).remove(j);
    }
    visited[i] = false; //there is a cycle only when once DFS, so we change it back when onece DFS is finished
    return true;
}

BFS:

    public boolean canFinishBFS(int numCourses, int[][] prerequisites) {
    if (numCourses <= 1)
        return true;
    ArrayList<HashSet<Integer>> edges = new ArrayList<HashSet<Integer>>(numCourses);
    int[] inDegree = new int[numCourses];
    Queue<Integer> q = new LinkedList<Integer>();
    int count = 0;

    for (int i = 0; i < numCourses; i++)
        edges.add(new HashSet<Integer>());

    for (int[] pre: prerequisites){
        if (!edges.get(pre[0]).contains(pre[1])){
            edges.get(pre[0]).add(pre[1]);
            inDegree[pre[1]]++;
        }
    }

    for (int i = 0; i < inDegree.length; i++)
        if (inDegree[i] == 0)
            q.add(i);

    while (!q.isEmpty()){
        int i = q.poll();
        count++;
        while (edges.get(i).size() != 0){
            int j = edges.get(i).iterator().next();
            if (--inDegree[j] == 0)
                q.add(j);
            edges.get(i).remove(j);
        }
    }

    return count == numCourses;
}

Simpler and more concise BFS solution:

Reference: https://leetcode.com/discuss/35578/easy-bfs-topological-sort-java

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;
}