207. Course Schedule

Leetcode Graph Depth-first Search Breath-first Search Topological Sort

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?

Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: 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.
You may assume that there are no duplicate edges in the input prerequisites.

分析¶

DFS的常见应用。检查有向图是不是DAG，即有没有环。详见Algorithms 4^th，思路很简单，如果在遍历了 $v->w$ 时，发现 $w$ 在栈上，那么说明肯定有环，因为既然 $w$ 在栈上，说明肯定有一条路径使得 $w->v$ 。

private boolean hasCycle;
public boolean canFinish(int numCourses, int[][] prerequisites) {
    hasCycle = false;
    // construct a graph
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++)
        graph.add(new ArrayList<Integer>());
    for (int[] prerequisite : prerequisites)
        graph.get(prerequisite[1]).add(prerequisite[0]);

    // dfs
    boolean[] mark = new boolean[numCourses];
    boolean[] onStack = new boolean[numCourses];
    for (int v = 0; v < numCourses; v++)
        if (!hasCycle & !mark[v]) 
            dfs(graph, mark, onStack, v);

    return !hasCycle;
}

private void dfs(List<List<Integer>> graph, boolean[] mark, boolean[] onStack, int v) {
    mark[v] = true;
    onStack[v] = true;
    for (int w : graph.get(v)) {
        if (!hasCycle & !mark[w])
            dfs(graph, mark, onStack, w);
        else if (onStack[w]) hasCycle = true;
    }
    onStack[v] = false;
}