Leetcode】210.course-schedule-ii

题目地址

https://leetcode.com/problems/course-schedule-ii/

题目大意

https://leetcode-cn.com/problems/course-schedule-ii

解题思路

有向图的拓扑排序，采用BFS解决。对每组数字，如[1,0], 实际可表示为一条从结点0指向结点1的边，对记录下每个结点的入度数。循环遍历每个结点，如果入度为0，表示没有需要上的课了，push到结果集合中，找不到入度为0的结点，就不需要进行下一次遍历。最后，如果集合中的结点数等于课程数，则返回该集合，否则返回空集合。

C++代码

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> in(numCourses, 0);
        vector<int> visit(numCourses, 0);
        for (vector<int> v : prerequisites) {
            in[v[0]]++;
        }
        vector<int> order;
        while(1) {
            bool flag = false;
            for (int i = 0; i < numCourses; i++) {
                if (in[i] == 0 && !visit[i]) {
                    order.push_back(i);
                    visit[i] = 1;
                    for (vector<int> v : prerequisites) {
                        if (v[1] == i) {
                            in[v[0]]--;
                        }
                    }
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
        
        if (order.size() != numCourses) {
            return {};
        }
        
        return order;

    }
};

Leetcode】210.course-schedule-ii

原文：https://www.cnblogs.com/AndrewGhost/p/12296472.html