力扣(LeetCode)207

摘要：所以这是可能的。示例输入输出解释总共有门课程。拓扑排序是来检测图中有无环的算法。删除中找到的点及以它为起点的边。代码邻接表表示法存放每个点的入度，初始为构造邻接表，并求出每个点的初始入度。暂存入度为的节点。

题目地址：
https://leetcode-cn.com/probl...
题目描述：
现在你总共有 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找到一个入度为0的点，若没有，则返回图中有环。
2删除1中找到的点及以它为起点的边。
3重复1、2直到图中所有点都被删除，此时返回图中无环。

下面的一种思路是建立类似邻接表的图，这里的邻接表保存的不是边，而是指向该点的
其他点，这种算法很好理解，但是时间复杂度过大。
思想是，每一次都找到一个点，这个点没有任何点指向它。然后把它删除。
再遍历图，把这个点作为起点的边(其他点邻接表的元素)删除，直到图为空返回true
或者找不到这个点，返回false。
java ac代码：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        
        //邻接表，存放的是指向该节点的其他节点编号，而不是边
        //如果某个点没有其他点指向它，那么对应的list为空。
        HashMap> map = new HashMap(numCourses);
        
        for(int i = 0;i < numCourses;i++)
            map.put(i,new ArrayList());
        
        for(int i = 0;i < prerequisites.length;i++)
        {
             int previous = prerequisites[i][1];
             int latter = prerequisites[i][0];
          
             Listlist = map.get(latter);
             list.add(previous);
        }
        while(map.size() > 0)
        {
            //判断是否能找到一个没有任何节点指向的节点
            boolean flag = false;
            int num = 0;
            for(Map.Entry> entry:map.entrySet())
            if(entry.getValue().size() == 0)
            {
                flag = true;
                num = entry.getKey();
                break;
            }

            if(!flag)return false;
            
            map.remove(num);
            Iterator> it = map.values().iterator();
            while(it.hasNext())
                it.next().remove(new Integer(num));
            
        }
        
        return true;
    }
}

下面这种是利用一个队列暂存入度为0的点的快速拓扑排序方法。
因为它不必每次都从头查找入度为0的点，因此时间效率得到了提示。
java ac代码：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        
        //邻接表,表示法
        HashMap> map = new HashMap(numCourses);
        
        //存放每个点的入度，初始为0
        HashMapmap2 = new HashMap(numCourses);
        
        for(int i = 0;i < numCourses;i++){
            map.put(i,new ArrayList());
            map2.put(i,0);   
        }
        
        //构造邻接表，并求出每个点的初始入度。
        for(int i = 0;i < prerequisites.length;i++)
        {
             int previous = prerequisites[i][1];
             int latter = prerequisites[i][0];
          
             Listlist = map.get(previous);
             list.add(latter);
             map.put(previous,list);
             map2.put(latter,map2.get(latter)+1);
        }
        
        //暂存入度为0的节点。
        ArrayDequequeue = new ArrayDeque();
        for(int i = 0;i < numCourses;i++)
            if(map2.get(i) == 0)
                queue.offer(i);
        
        //统计最终能有多少个入度为0的点，若该数量小于numCourses则代表有环
        int count = 0;
        while(!queue.isEmpty())
        {
         int node = queue.poll();   
         for(int i:map.get(node))
         {
             int ii = map2.get(i);
             ii -= 1;
             if(ii != 0)
                map2.put(i,ii);
             //这个点的入度变为了0，可以加入队列中
             else
             queue.offer(i);
         }
          
         count++;
        }
       
        
        return count == numCourses;
    }
}