207. Course Schedule

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?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
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. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

click to show more hints.
Hints:This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.

思路是BFS + Topological sort,跟 Course Schedule ii 很类似。用两个HashMap表示入度和Graph. 建立queue来遍历节点,先把入度为零的点offer到queue里面,再一个一个poll出来遍历。用courseRemaining来记录还需要遍历的节点。每次遍历某个节点,要使得它的neighbors的入度减一。(就是当前节点指向的点,在这里就是以当前节点作为先修课的课程)如果neighbors当中有节点在入度减一后入度为零,要将其加入到queue里面,同时courseRemaining自减。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 1){
            return true;
        }
        if (prerequisites.length == 0 || prerequisites[0].length == 0){
            return true;
        }
        Map<Integer, Integer> indegree = new HashMap<>();
        Map<Integer, Set<Integer>> neighbors = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < prerequisites.length; i++){
           
            if (indegree.containsKey(prerequisites[i][0])){
                indegree.put(prerequisites[i][0], indegree.get(prerequisites[i][0]) + 1);
            } else {
                indegree.put(prerequisites[i][0], 1);
            }
        }
        int coursesRemaining = numCourses;
        for (int i = 0; i < numCourses; i++){
            if (!indegree.containsKey(i)){
                queue.offer(i);
                coursesRemaining--;
            }
            neighbors.put(i, new HashSet<Integer>());
        }
        for (int i = 0; i < prerequisites.length; i++){
            neighbors.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }

        while (!queue.isEmpty()){
            Integer curt = queue.poll();
            for(Integer nei : neighbors.get(curt)){
                indegree.put(nei, indegree.get(nei) - 1);
                if (indegree.get(nei) == 0){
                    queue.offer(nei);
                    coursesRemaining--;
                }
            }
        }
        // System.out.print(coursesRemaining);
        return coursesRemaining == 0;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,834评论 0 23
  • 灯黑了那一整夜,睡不着,躺在阁楼上。楼下是爷爷刚安息的灵位,父亲和姑姑正在为爷爷彻夜守灵。已经是午夜12时了,寂静...
    陈仲夏阅读 315评论 0 2
  • 也是晕了 爸妈房间的空调竟然坏了 由于我一直喊木有零食 妈咪给我买了一堆零食 感觉自己在家就是次了睡 睡了次
    角落蜷缩阅读 139评论 0 0
  • 到了中年,那种奋发有为的精神状态锐减,倒是想着上有老、下有小这种境况下,自己健康才能承受赡养和抚养责任的事...
    认识就是缘阅读 532评论 0 1
  • 工作忙,身体累,国企巨轮未熬一甲子。 味道美,价格廉,沙棉小吃回忆三代人。 临江仙,沙棉小吃。 客似云来常聚往,曾...
    徐云喜阅读 919评论 9 5