[LeetCode] 207. Course Schedule

ephererid 发布于2019-08-15 17:47 / 551人阅读

Problem

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

Solution

class Solution {
    public boolean canFinish(int num, int[][] pre) {
        //initialize graph: create list for each node(int)
        if (pre.length > num*(num-1)/2) return false;
        List[] graph = new ArrayList[num];
        for (int i = 0; i < num; i++) graph[i] = new ArrayList<>();
        
        //build graph: save children nodes to the corresponding list
        //save indegrees of children nodes to indegree[] array
        int[] indegree = new int[num];
        for (int i = 0; i < pre.length; i++) {
            indegree[pre[i][0]]++;
            graph[pre[i][1]].add(pre[i][0]);
        }
        
        //create queue to do BFS
        //save parent nodes which don"t have pre courses (indegree == 0) to the queue
        Deque queue = new ArrayDeque<>();
        for (int i = 0; i < num; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }
        
        //BFS: poll the parent nodes, if they have children, offer to the queue
        int count = 0;
        while (!queue.isEmpty()) {
            Integer root = queue.poll();
            count++;
            List children = graph[root];
            for (int child: children) {
                if (indegree[child] == 1) {
                    queue.offer(child);
                }
                indegree[child]--;
            }
        }
        
        return count == num;
    }
}

GPU云服务器云服务器 Course v207 LeetCode Schedule

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69443.html

207. Course Schedule

摘要：题目解答这是一个有向图问题，所以先建图，然后再扫。同时记录一共存了多少课程在里，这些课都是可以上的课。如果当两个点在同时访问的时候，那么构成死循环，返回。扫完所有的点都没问题，才返回。这里总是忘记，当中时，才否则继续循环题目：There are a total of n courses you have to take, labeled from 0 to n - 1. Some c...

Nino 2019-08-14 14:17 评论0 收藏0
[LeetCode] 210. Course Schedule II

Problem 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...

zhkai 2019-08-19 11:12 评论0 收藏0
[Leetcode] Course Schedule 课程计划

Course Schedule I 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 e...

Amio 2019-08-14 12:40 评论0 收藏0
[LeetCode/LintCode] Course Schedule II

Problem 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 a...

Lavender 2019-08-15 17:49 评论0 收藏0
210. Course Schedule II

摘要：建立入度组成，把原来输入的无规律，转换成另一种表示图的方法。找到为零的点，放到里，也就是我们图的入口。对于它的也就是指向的。如果这些的入度也变成，也就变成了新的入口，加入到里，重复返回结果。这里题目有可能没有预修课，可以直接上任意课程。 Some courses may have prerequisites, for example to take course 0 you have ...

lbool 2019-08-16 10:36 评论0 收藏0