LeetCode 207. Course Schedule

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.

大致意思就是给定我们一定数量的课程，以及课程间的先修关系，让我们判断是否可以修完所有课程。
该问题等价于判断一个有向图是否有环，如果有环，就无法对该有向图进行拓扑排序，也就无法在满足课程间的先修关系的前提下修完所有课程。
我们可以依次从每个顶点开始使用DFS进行图的搜索，一旦发现环即可断定无法修完所有课程。为了提高效率，本算法加了一个回溯拆边的操作，因为既然已经确认这条路径上没有环，就不需要重复访问了。
代码如下：

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        boolean[] visited = new boolean[numCourses];    // 访问标志
        List<Integer>[] adj = new List[numCourses];     // 邻接链表
        for(int i = 0; i < numCourses; i++)
            adj[i] = new ArrayList<Integer>();
        for(int i = 0; i < prerequisites.length; i++)   // 由偏序关系构造邻接链表
        {
            int curCourse = prerequisites[i][0];        
            int preCourse = prerequisites[i][1];        
            adj[preCourse].add(curCourse);
        }
        for(int i = 0; i < numCourses; i++) // 从每一个结为起点开始做DFS，每次循环visited数组元素均为false
        {
            if(!dfs(adj, visited, i))       // 任意一次DFS发现环均可断定无法修完所有课程
                return false;
        }
        return true;
    }

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

        if(visited[course])     // 再次访问访问过的结点，有环
            return false;
        visited[course] = true;
        for (int i = 0; i < adj[course].size(); i++)
        {
            if(!dfs(adj, visited, adj[course].get(i)))
                return false;
            adj[course].remove(i);  // 未发现环，依次拆掉走过的边，避免再走这条路
        }
        visited[course] = false;    // 标志复位，向上回溯
        return true;
    }
}

解决本题的另一种方法是使用BFS，以无需先修的课程为起点，根据课程间的偏序关系搜索其他课程，统计搜索到（修完）的课程数，与总课程数进行比较即可判断是否可以修完所有课程，代码如下：

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        List<Integer>[] adj = new List[numCourses];     // 邻接链表
        for(int i = 0; i < numCourses; i++)
            adj[i] = new ArrayList<Integer>();
        int[] indegree = new int[numCourses];           // 入度，即所需先修课程数
        Queue<Integer> readyCourses = new LinkedList(); // 可修课程队列
        int finishCount = 0;                            // 修完的课程数  

        for (int i = 0; i < prerequisites.length; i++)  // 由偏序关系构造邻接链表，并统计入度
        {
            int curCourse = prerequisites[i][0];        
            int preCourse = prerequisites[i][1];        
            adj[preCourse].add(curCourse);
            indegree[curCourse]++;
        }
        for (int i = 0; i < numCourses; i++) 
        {
            if (indegree[i] == 0) 
                readyCourses.offer(i);             // 无需先修的课程先入队列
        }
        while (!readyCourses.isEmpty()) 
        {
            int course = readyCourses.poll();      // 出队列，即修完该课程
            finishCount++;
            for (int nextCourse : adj[course]) 
            {
                indegree[nextCourse]--;
                if (indegree[nextCourse] == 0)     // 所有先修课程已修完，入队列
                    readyCourses.offer(nextCourse);
            }
        }
        return finishCount == numCourses;
    }
}