[LintCode] 615 Course Schedule 解题报告

Description
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
Given n = 2, prerequisites = [[1,0]]
Return true

Given n = 2, prerequisites = [[1,0],[0,1]]
Return false


思路
这题其实就是问的能不能做出一个topological sort出来。也就是问这个图有没有cycle。
LintCode写的DFS过不去因为stackoverflow了。
思路就是先把图给做出来。然后对vertex进行dfs，维护一个叫onStack的数组记录dfs在每一个stack上访问过的v的状态。如果我们发现正在访问的点在stack上的状态是已经访问过，那么说明有一个环又回来到这个点了。那么就有cycle了。

DFS的解
Code

public class Solution {
    /**
     * @param numCourses a total of n courses
     * @param prerequisites a list of prerequisite pairs
     * @return true if can finish all courses or false
     */
     
    private boolean[] onStack;
    private boolean[] marked;
    private boolean hasCycle;
    private HashMap<Integer, ArrayList<Integer>> adj;
        
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Write your code here
        
        adj = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            adj.put(i, new ArrayList<Integer>());
        }
        
        for (int i = 0; i < prerequisites.length; i++) {
            adj.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        
        onStack = new boolean[numCourses];
        marked = new boolean[numCourses];
        hasCycle = false;
        
        for (int v = 0; v < numCourses; v++) {
            if (!marked[v]) {
                dfs(v);
            }
            if (hasCycle) {
                return false;
            }
        }
        
        return !hasCycle;
    }
    
    public void dfs(int v) {
        
        onStack[v] = true;
        marked[v] = true;
        for (int w : adj.get(v)) {
            if (hasCycle) {
                return;
            }
            else if (!marked[w]) {
                dfs(w);
            }
            else if (onStack[w]) {
                hasCycle = true;
                break;
            }
        }
        
        if (hasCycle) {
            return;
        }
        
        onStack[v] = false;
    }
}

BFS:

Kahn's algorithm

One of these algorithms, first described by Kahn (1962), works by choosing vertices in the same order as the eventual topological sort. First, find a list of "start nodes" which have no incoming edges and insert them into a set S; at least one such node must exist in a non-empty acyclic graph. Then:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

If the graph is a DAG, a solution will be contained in the list L (the solution is not necessarily unique). Otherwise, the graph must have at least one cycle and therefore a topological sorting is impossible.

Reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack. Depending on the order that nodes n are removed from set S, a different solution is created. A variation of Kahn's algorithm that breaks ties lexicographically forms a key component of the Coffman–Graham algorithm for parallel scheduling and layered graph drawing.

BFS的解
Code

public class Solution {
    /**
     * @param numCourses a total of n courses
     * @param prerequisites a list of prerequisite pairs
     * @return true if can finish all courses or false
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Write your code here
        
        ArrayList<Integer>[] adj = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses];
        
        for (int course = 0; course < numCourses; course++) {
            adj[course] = new ArrayList<Integer>();
        }
        
        for (int i = 0; i < prerequisites.length; i++) {
            adj[prerequisites[i][1]].add(prerequisites[i][0]);
            inDegree[prerequisites[i][0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < inDegree.length; i++){
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int count = 0;
        while (!queue.isEmpty()) {
            int v = queue.poll();
            count++;
            int n = adj[v].size();
            for (int i = 0; i < n; i++) {
                inDegree[adj[v].get(i)]--;
                if(inDegree[adj[v].get(i)] == 0) {
                    queue.offer(adj[v].get(i));
                }
            }
        }

        return count == numCourses;
    }
}