000图中等 leetcode207. 课程表_课程表怎么遍历

207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] incnt = new int[numCourses];
        Queue<Integer> que = new LinkedList<>();
        int cnt = 0;
        for(int[] pre : prerequisites){
            incnt[pre[0]]++; 
        }

        for(int i = 0; i < incnt.length; i++){
            if(incnt[i] == 0){
                que.offer(i);
            }
        }

        while(!que.isEmpty()){
            int tmp = que.poll();
            cnt++;
            for(int[] pre : prerequisites){
                if(pre[1] == tmp){
                    incnt[pre[0]]--;
                    if(incnt[pre[0]] == 0){
                        que.offer(pre[0]);
                    }
                }
            }
        }
        return cnt == numCourses;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import java.util.LinkedList;
import java.util.ArrayList;
class Solution {
    /*
    刚开始看题解没明白indegree[arr[0]]++为什么就是在统计每个结点的入度
    首先不是所有的选修课程都有必修课程前提，prerequisites是描述前驱关系的，若一个课程X(0<=x<=numCourses)并没有出现在prerequisites中，
    说明这个课程x没有前驱结点,即没有必修课程前提。

    一个课程没有必修课程(入度为零)或着必修课程都可以正常学习(入度可以减少为零)则该课程可以学习，
    这样的课程数量为numCourses，则说明所有的课程可以学习返回true.
    
    1.计算每个课程的入度
    2.描述课程的邻接表（存放每个结点后继结点的集合）
    3.将入度为零的结点加入队列
    4.队列出头结点，sum自增一，并且把头结点的后继结点的入度减一
    5.当sum等于numCourses，则说明所有的课程可以学习
    */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(numCourses == 0){
            return true;
        }
        int[] indegree = new int [numCourses];
        //1.遍历prerequisites，计算每个课程的入度,prerequisites中没有的课程入度默认为0
        for(int i = 0; i < prerequisites.length; i++){
            indegree[prerequisites[i][0]]++;
        }

        //2.构建描述课程的邻接表
        List<Integer>[] adj = new List[numCourses];
        //这个for循环很必要，不然后面赋值会报空指针异常
        for(int i = 0 ; i < numCourses; i++){
            adj[i] = new ArrayList<>();
        }
        for(int i = 0; i < prerequisites.length; i++){
            adj[prerequisites[i][1]].add(prerequisites[i][0]);
        }

        //建一个队列
        Queue<Integer> queue = new LinkedList<>();

        //3.将入度为零的结点加入队列
        for(int i = 0; i < numCourses; i++){
            if(indegree[i] == 0){
                queue.offer(i);
            }
        }
        //统计有多少个入读为零的结点（课程）
        int sum = 0;
        while(!queue.isEmpty()){
            int tmp = queue.poll();
            sum++;
            List<Integer> li = adj[tmp];
            //把这个结点后继的结点入度减一
            for(int past: li){
                indegree[past]--;
                if(indegree[past] == 0){
                    queue.add(past);
                }
            }
        }
        return sum == numCourses;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63