Course Schedule II

This week is still a matter of plans
210 questions on LeetCode: https://leetcode.com/problems/course-schedule-ii

subject

Given n courses, some courses need the preparatory knowledge of other courses, that is, only after learning other courses can we learn this course. [1, 0] means that to learn 1 course, you must first learn 0 course. Give the number of such sides and courses, and output a sequence of learning courses.

Example1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .

Example 2 :

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Title Solution

After careful consideration of the problem, we can see that the solution to the problem is a sequence of topological ordering. The so-called topological ordering is a sequence of all nodes in the graph. The sequence satisfies the following conditions: for each edge [u, v], u in the sequence must be before v. So there is no ring in the graph.

There are several ways to find the topological sequence. One is to find the node with entry degree of 0 in the graph, add it to the sorting, delete the edge starting from the node, continue to find the node with entry degree of 0, and loop until there is no node with entry degree of 0. DFS algorithm can also be used to traverse the graph and record the completion order of each node. The descending order of node completion order is a topological sequence. The first algorithm is used here.

Code

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int>> adjacent_list(numCourses);
        vector<int> in_degree(numCourses);
        queue<int> _queue;
        vector<int> res;

        for (auto &edge : prerequisites) {
            adjacent_list[edge.second].push_back(edge.first);
            in_degree[edge.first]++;
        }

        for (int i = 0; i < numCourses; i++) {
            if (in_degree[i] == 0) {
                _queue.push(i);
            }
        }

        while (_queue.size()) {
            int vetrix = _queue.front();
            for (auto v : adjacent_list[vetrix]) {
                if (--in_degree[v] == 0) {
                    _queue.push(v);
                }
            }
            res.push_back(vetrix);
            _queue.pop();
        }

        return res.size() == numCourses ? res : vector<int>();
    }
};