leetcode 210. Course Schedule II | 210. 课程表 II（Java）

约定不等于承诺〃 2022-10-06 11:56 202阅读 0赞

## 题目 ##

[https://leetcode.com/problems/course-schedule-ii/][https_leetcode.com_problems_course-schedule-ii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

本题与 [leetcode 207. Course Schedule][] 基本相同，代码只需要稍作修改，将图的遍历顺序记录在一个 list 中。

import java.util.ArrayList;
    import java.util.Collections;
    
    class Node { 
        int inDegree;
        ArrayList<Integer> children;
        boolean alive;
    
        public Node() { 
            alive = true;
            children = new ArrayList<>();
        }
    }
    
    class Solution { 
        public int[] findOrder(int numCourses, int[][] prerequisites) { 
            ArrayList<Integer> list = new ArrayList<>();
            // init courses
            Node[] nodes = new Node[numCourses];
            for (int i = 0; i < numCourses; i++) { 
                nodes[i] = new Node();
            }
            // init prerequisites
            for (int i = 0; i < prerequisites.length; i++) { 
                nodes[prerequisites[i][0]].children.add(prerequisites[i][1]);
                nodes[prerequisites[i][1]].inDegree++;
            }
            // check DAG
            int remain = numCourses; // remaining nodes
            boolean valid = true; // last loop really works
            while (valid && remain > 0) { 
                valid = false;
                for (int i = 0; i < numCourses; i++) { 
                    if (nodes[i].inDegree == 0 && nodes[i].alive) { 
                        list.add(i);
                        for (int n : nodes[i].children) {  // update
                            nodes[n].inDegree--;
                        }
                        valid = true;
                        nodes[i].alive = false;
                        remain--;
                    }
                }
            }
            // for return
            if (remain == 0) { 
                Collections.reverse(list);
                int[] ints = new int[list.size()];
                int i = 0;
                for (Integer n : list) { 
                    ints[i++] = n;
                }
                return ints;
            } else return new int[]{ };
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

[https_leetcode.com_problems_course-schedule-ii]: https://leetcode.com/problems/course-schedule-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/aca3cc4697d847399afb61df3a3db689.png
[leetcode 207. Course Schedule]: https://hanquan.blog.csdn.net/article/details/117733407
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/c5f3cb53f7f240a9acf2ca8f1637413a.png