207. Course Schedule

Medium

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:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

Solution:

DFS O(V+E) : 不仅由点决定，同时由边决定。边很多或则点很多。

         There is a cycle only if there is a back edge present in the graph. to detect the back edge, we keep track of the vertexes in current recursion stack of function for DFS traversal. if we reach out a vertex which is already in the current recursion stack, then there is a cycle in graph. the edge that connects current vertex to the vertex in current recursion stack is back edge. we use the recStack array to keep track of the current vertex in current stack.

因为是 detect cycle，只要判断 topological order 是否存在，而并不需要得到具体的 order，所以不用使用 Stack，只用一个 boolean[] onStack 记录入栈过的元素即可。另外，用 boolean[] visited 记录访问过的 vertices，如果之前访问过则不再访问。

• 在搜索每条 path 的过程中将访问过的 vertices 的 marked[v] 和 onStack[v] 标记为 true，当该条 path 搜索完返回时将 onStack[v] 恢复成 false，而 marked[v] 不变；

• 在搜索一条新 path 时之前搜过的 path 上的 vertices 都不用再访问，只要看当前访问到的 vertex 和当前 path 上的某一点是否相连，如果相连则构成 cycle。

为什么可以选任意节点dfs？

因为先将后代先放进stack，然后遍历到祖先的时候，祖先才放进stack。

先从0开始遍历，0没有后代，push0，1没有后代，push1，2有3，3，没有后代，push 3， 2的后代都遍历完，push2.4的后代都遍历完，push4， 5的后代都遍历完，push5.

push 0 1 3 2 4 5

所以即使2先遍历也不会影响5 2 3 的优先关系。

    public class Graph{
        public int vertex; // No. of vertices 

         // Array  of lists for Adjacency List Representation 

public LinkedList<Integer>[] adj; //

        public Graph(int numCourses, int[][] pre){
            this.vertex = numCourses;
            adj = new LinkedList[this.vertex];//初始化数组对象
            for(int i = 0; i < vertex; i++){
                adj[i] = new LinkedList<Integer>();//初始化每个元素
            }
            for(int i = 0; i < pre.length; i++){
                int from = pre[i][1];
                int to = pre[i][0];
                adj[from].add(to);
            }
        }
        
        public boolean isCycle(){
            boolean[] curStack = new boolean[vertex];
            boolean[] visited = new boolean[vertex];
            for(int i = 0 ; i < vertex; i++){
                if(!visited[i]){
                    if(dfsUtil(i,curStack,visited))
                        return true;;
                }
            }
            return false;
        }
        
        public boolean dfsUtil(int index, boolean[] curStack, boolean[] visited){
//            if(curStack[index]){
//                return true;
//            }

         // Mark the current node as visited and 

        // part of recursion stack
curStack[index] = true;
            visited[index] = true;
            LinkedList<Integer> children = this.adj[index];
            for(Integer to : children){
             if(curStack[to]) {
              return true;
             }else if(!visited[to] && dfsUtil(to,curStack,visited)){
                    return true;
                }
            }
            curStack[index] = false;
            return false;
        }
    }
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Graph g = new Graph(numCourses,prerequisites);
        if(g.isCycle()){
            return false;
        }
        return true;
    }

2 BFS： O(V+E)
需要一个queue存入度为0的Vertice,Vertex的入度（指向该点的vertex的数量）用int[] inDegree记录。
从inDegree[i]为0的vertex开始，将它出栈。并将所有adjacent vertice的inDegree减1，并将inDegree[i] == 0 的vertex入栈。重复上述过程知道Q为空。
如果Q为空，还有vertice没有入栈，则存在环。如下图，明明有3个点，却没有入度为0的点，所以存在环。

class Solution {
    public class Graph{
        public int vertex;
        public LinkedList<Integer>[] adj;
        public int[] inDegree;
        public Graph(int numCourses, int[][] pre){
            this.vertex = numCourses;
            adj = new LinkedList[this.vertex];
            inDegree = new int[this.vertex];
            for(int i = 0; i < vertex; i++){
                adj[i] = new LinkedList<Integer>();
            }
            for(int i = 0; i < pre.length; i++){
                int from = pre[i][1];
                int to = pre[i][0];
                adj[from].add(to);
                inDegree[to]++;
            }
        }
    }   
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Graph g = new Graph(numCourses,prerequisites);
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i = 0; i < g.vertex; i++){
            if(g.inDegree[i] == 0){
                q.add(i);
            }
        }
        int count = 0;
        while(!q.isEmpty()){
            int vertex = q.poll();
            count++;
            LinkedList<Integer> children = g.adj[vertex];
            for(Integer to: children){
                g.inDegree[to]--;
                if(g.inDegree[to] == 0){
                    q.add(to);
                }
            }
        }
        if(count<numCourses) return false;
        else return true;
    }
}