Course Schedule

想法：

1. 建ArrayList[]不能用泛型，list.get(i)默认返回Object，需要cast一下。
2. 这类题自己先把graph建出来，如果是用DFS做，那就要维护一个visited数组，来check有没有环。如果是用BFS来做，就维护一个indegree数组，每次只把indegree为0的点放进queue里去做BFS。

Course Schedule I, DFS解法。

这题搞了好久，参考了一个挺好的解法，就是自己建图，方法是建一个ArrayList[]数组，ArrayList[i]代表了vertex i, 然后ArrayList[i]里的元素代表了和vertex i相连的点，即模拟了edges，这样就把图建出来了。

这题的本质就是，给你一个代表graph的adjacency array, 判断是否有环。其实和Graph Valid Tree非常像。另外维护一个visited数组，数值等于0表示还没访问过的，数值等于1表示正在访问的，数值等于2表示访问完了的。然后如果在dfs的过程中碰到了数值等于1的点，说明有环。否则在dfs结束的时候，把这个点设为2，表示访问完了。

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] visited = new int[numCourses];

        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        for (int[] p: prerequisites) {
            int vertex = p[1];
            int adjacent = p[0];

            graph[vertex].add(adjacent);
        }

        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0 && dfs(graph, visited, i)) {
                return false;
            }
        }

        return true;
    }

    private boolean dfs(ArrayList[] graph, int[] visited, int course) {
        visited[course] = 1;
        boolean hasCycle = false;

        for (int i = 0; i < graph[course].size(); i++) {
            int next = (int) graph[course].get(i);
            if (visited[next] == 1) {
                return true;
            } else if (visited[next] == 0) {
                hasCycle = hasCycle || dfs(graph, visited, next);
            }
        }

        visited[course] = 2;
        return hasCycle;
    }
}

Course Schedule I, BFS解法。 和之前的做法一样，用ArrayList[]把图建出来，同时维护一个indegree，把indegree[vertex] == 0的点放到queue里去遍历。如果graph有环，会出现有环的部分永远无法进入BFS被访问，因此在结尾我们只需看一下到底有没有点没有被访问过。

这种情况的问题和当初面试时候问为什么Java GC里不只依靠reference counting做的问题一样，就是当某个局部出现环时，无法通过BFS建reference count的方式，使所有点的当前count == 0, 因为所有点的indegree都非0，无从开始。

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];

        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        for (int[] p: prerequisites) {
            int vertext = p[1];
            int adjacent = p[0];
            graph[vertext].add(adjacent);
            indegree[adjacent]++;
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int visitedCount = 0;
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            visitedCount++;

            for (int i = 0; i < graph[vertex].size(); i++) {
                int next = (int) graph[vertex].get(i);
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return visitedCount == numCourses;
    }
}

Course Schedule II, DFS解法，跟I的代码几乎一样，就是在dfs的方法里，多加了一个LinkedList的参数，每次一个点访问完了，把这个点加到LinkedList的头上去。

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] visited = new int[numCourses];

        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        for (int[] p: prerequisites) {
            int vertex = p[1];
            int adjacent = p[0];
            graph[vertex].add(adjacent);
        }

        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0 && dfs(list, graph, visited, i)) {
                return new int[0];
            }
        }

        int[] result = new int[numCourses];
        for (int i = 0; i < result.length; i++) {
            result[i] = list.get(i);
        }

        return result;
    }

    private boolean dfs(LinkedList<Integer> list, ArrayList[] graph, int[] visited, int course) {
        visited[course] = 1;
        boolean hasCycle = false;

        for (int i = 0; i < graph[course].size(); i++) {
            int next = (int) graph[course].get(i);
            if (visited[next] == 1) {
                return true;
            } else if (visited[next] == 0) {
                hasCycle = hasCycle || dfs(list, graph, visited, next);
            }
        }

        visited[course] = 2;
        list.addFirst(course);
        return hasCycle;
    }
}

Course Schedule II, BFS解法，和I的代码还是基本一样的。

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];

        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        for (int[] p: prerequisites) {
            int vertext = p[1];
            int adjacent = p[0];
            graph[vertext].add(adjacent);
            indegree[adjacent]++;
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int visitedCount = 0;
        int[] result = new int[numCourses];
        while (!queue.isEmpty()) {
            int course = queue.poll();
            result[visitedCount++] = course;

            for (int i = 0; i < graph[course].size(); i++) {
                int next = (int) graph[course].get(i);
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return visitedCount == numCourses ? result : new int[0];
    }
}