代码随想录训练营第47天休息日|210.课程表II

210.课程表II

思路

拓扑排序
将入度为0的节点放入队列，将队列中点的入度置为-1，当前访问点的后继入度减1，
迭代直至没有入度为0的节点
仍存在入度大于0的节点，说明图中有环，不能学完

代码

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] inDegrees = new int[numCourses];
        List<Integer> res = new ArrayList<>();
        int i, j, n, srcNum;
        n = prerequisites.length;
        srcNum = numCourses;
        int src, tgt;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (i = 0; i < n; ++i) {
            tgt = prerequisites[i][0];
            src = prerequisites[i][1];
            if (inDegrees[tgt] == 0) {
                --srcNum;
            }
            ++inDegrees[tgt];
            if (!map.containsKey(src)) {
                map.put(src, new ArrayList<Integer>());
            }
            map.get(src).add(tgt);
        }
        j = 0;
        while (srcNum > 0) {
            for (i = 0; i < numCourses; ++i) {
                if (inDegrees[i] == 0) {
                    res.add(i);
                    --inDegrees[i];
                    --srcNum;
                }
            }
            while (j < res.size()) {
                if (map.containsKey(res.get(j))) {
                    for (Integer k: map.get(res.get(j))) {
                        if (--inDegrees[k] == 0) {
                            ++srcNum;
                        }
                    }
                }
                ++j;
            }
        }
        if (res.size() < numCourses) {
            return new int[0];
        }
        int[] ans = new int[numCourses];
        for (i = 0; i < numCourses; ++i) {
            ans[i] = res.get(i);
        }
        return ans;
    }
}
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

总结

振作一下