207.课程表

题目描述：

现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例1：

输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例2：

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

解法1：kahn算法

kahn算法是求图的拓扑排序的经典算法，其主要步骤如下：
1、获取每个节点的入度；
2、将入度为0的节点推入栈；
3、while(栈非空)
取出栈顶节点，删除所有以其为起点的边，如果删除后终点节点入度为0，则将其压入栈。
4、如果图中还存在节点，则不存在拓扑排序。

具体实现如下：

        int[] indegrees = new int[numCourses];
        for(int[] cp : prerequisites) 
        {
            indegrees[cp[0]]++;//获取入度
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++)
        {
            if(indegrees[i] == 0) 
            {
                queue.addLast(i);//将入度为0的节点压栈
            }
        }
        while(!queue.isEmpty())
        {
            Integer pre = queue.removeFirst();
            numCourses--;
            for(int[] req : prerequisites) 
            {
                if(req[1] != pre) 
                {
                    continue;
                }
                if(--indegrees[req[0]] == 0) //删除以其为起点的边
                {
                    queue.add(req[0]);//若终点节点入度为0，将其压入栈
                }
            }
        }
        return numCourses == 0;

解法2：深度优先搜索

在一次深度优先搜索中，如果访问到了起始节点，则证明该图有环。即从某一节点出发进行深度优先搜索，若回到该节点，则有环。对于有环的图，不存在拓扑排序。
但是需要对其他节点出发访问到的节点和当前节点出发访问到的节点进行区分。
将由节点i出发访问到的所有节点的vis值设为1，当以i为起点开始的DFS结束后，将其vis值设置为-1。当其他轮次的DFS遇到vis==-1的节点时，直接跳过。遇到vis==1的节点则证明该节点是当前轮次DFS遍历过的节点，故存在环。
具体实现如下：

Boolean DFS(ArrayList<ArrayList<Integer>> G, int[] vis, int node)
    {
        if(vis[node] == -1)
        {
            return false;
        }
        if(vis[node] == 1)
        {
            return true;
        }
        vis[node] = 1;
        for(int i : G.get(node))
        {
            if(DFS(G, vis, i))
            {
                return false;
            }
        }
        vis[node] = -1;
        return false;
    }
public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList<ArrayList<Integer>> G = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<numCourses;i++)
        {
            ArrayList<Integer> t = new ArrayList<Integer>();
            G.add(t);
        }
        for(int[] t : prerequisites)
        {
            G.get(t[1]).add(t[0]);
        }
        int[] vis = new int[numCourses];
        for(int i=0;i<numCourses;i++)
        {
            if(DFS(G, vis, i))
            {
                return false;
            }
        }
        return true;
    }