Leetcode 207 - study Java code, source code reference: http://www.jianshu.com/p/deceb6173865

Leetcode207_studycode.java

/*
source code from http://www.jianshu.com/p/deceb6173865
*/
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 1 || prerequisites == null || prerequisites.length == 0) {
            return true;
        }
        ArrayList<Integer>[] graph = new ArrayList[numCourses];
        // 把int[][]转换成adjacency list
        // 在graph中，index是每一个课程
        // 所连接的arraylist是这个课程所相连的其他所有课程
        for (int i = 0; i < prerequisites.length; i++) {
            if (graph[prerequisites[i][0]] == null) {
                graph[prerequisites[i][0]] = new ArrayList<>();
            }
            graph[prerequisites[i][0]].add(prerequisites[i][1]);
        }
        // mark每个cell中具有3个值，0,1,2
        // 0 代表 没有被访问过
        // 1 代表 正在被访问
        int[] mark = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(mark, graph, i)) {
                return false;
            }
        }

        return true;
    }

    private boolean dfs(int[] mark, ArrayList[] graph, int course) {
        if (mark[course] == 1) {
            return false;
        } else if (mark[course] == 2) {
            return true;
        } else {
            mark[course] = 1; // 现在正在访问中
        }

        // 继续访问该课程相连的所有课程
        if (graph[course] != null) {
            for (int i = 0; i < graph[course].size(); i++) {
                if (!dfs(mark, graph, (int)graph[course].get(i))) {
                    return false;
                }
            }
        }
        
        mark[course] = 2;
        return true;
    }
}