Classic topological sorting problem -- leetcode207 curriculum +leetcode210 curriculum II

Topic content

You must take this semester numCourses Courses , Write it down as 0 To numCourses - 1 .

Before you take some courses, you need some prerequisite courses . Prerequisite courses by array prerequisites give , among prerequisites[i] = [ai, bi] , If you want to learn a course ai be must Learn the course first bi .

for example , The prerequisite course is right for [0, 1] Express ： Want to learn the course 0 , You need to finish the course first 1 .
Please judge whether it is possible to complete all the courses ？ If possible , return true ; otherwise , return false .

Example 1：

Input ：numCourses = 2, prerequisites = [[1,0]]
Output ：true
explain ： All in all 2 Courses . Study the course 1 Before , You need to complete the course 0 . It's possible .

Example 2：

Input ：numCourses = 2, prerequisites = [[1,0],[0,1]]
Output ：false
explain ： All in all 2 Courses . Study the course 1 Before , You need to finish ​ Course 0 ; And study the course 0 Before , You should also finish the course first 1 . It's impossible .

source ： Power button （LeetCode） link ：https://leetcode.cn/problems/course-schedule
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

This is actually a classic topological sorting problem , The longest solution is to eliminate the completed node event and its path , Then find a read-in as 0 Just a little . therefore , We need a map, Save a point of penetration . Find all entries of 0 The point of , There is a queue . And then a little bit , Outgoing queue , All his neighbors' degrees -1. Restart traversal , Until the queue is empty .
But write it down according to this idea , When I write, I feel like I'm not very good , Count the number of cycles , May get stuck TLE, But the main thing is that apart from this idea, I have no other feasible good ideas , Just try , I didn't expect to AC, If you don't understand the elegant code , You can also look at my simple and rude .（ Still need to learn good code ）

class Solution {
    
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    
        map<int,int> tu;
        set<int> visit;
        int m=prerequisites.size();
        for(int i=0;i<numCourses;i++){
    
            // vector<int> mid;
            tu.insert(pair<int,int>(i,0));
        }
        for(int i=0;i<m;i++){
    
            // if(tu.find(prerequisites[i][0])==tu.end()){
    
            // vector<int> mid;
            // mid.push_back(prerequisites[i][1]);
            // tu.insert(pair<int,vector<int>>(i,mid));
            // }
            // else{
    
            tu[prerequisites[i][0]]++;
            // }
        }
        queue<int> link;
        for(int i=0;i<numCourses;i++){
    
            if(tu[i]==0){
    
                link.push(i);
                visit.insert(i);
            }
        }
        while(!link.empty()){
    
            int biao=link.front();
            link.pop();
            cout<<biao<<" ";
            for(int i=0;i<m;i++){
    
                if(prerequisites[i][1]==biao){
    
                    tu[prerequisites[i][0]]--;
                }
            }
            for(int i=0;i<numCourses;i++){
    
                if(tu[i]==0&&visit.find(i)==visit.end()){
    
                    link.push(i);
                    visit.insert(i);
                }
            }
        }
        return visit.size()==numCourses;
    }
};

Curriculum advanced version of the curriculum II—— Topic content

Now you have numCourses Courses need to be selected , Write it down as 0 To numCourses - 1. Give you an array prerequisites , among prerequisites[i] = [ai, bi] , In elective courses ai front must First elective bi .

for example , Want to learn the course 0 , You need to finish the course first 1 , We use a match to represent ：[0,1] .
Return to the learning order you arranged to complete all the courses . There may be more than one correct order , You just go back Any one That's all right. . If it is not possible to complete all the courses , return An empty array .

Example 1：

Input ：numCourses = 2, prerequisites = [[1,0]]
Output ：[0,1]
explain ： All in all 2 Courses . To learn the course 1, You need to finish the course first 0. therefore , The correct order of courses is [0,1] .

Example 2：

Input ：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output ：[0,2,1,3]
explain ： All in all 4 Courses . To learn the course 3, You should finish the course first 1 And courses 2. And the curriculum 1 And courses 2 They should all be in the class 0 after .
therefore , A correct sequence of courses is [0,1,2,3] . The other right sort is [0,2,1,3] .

Example 3：

Input ：numCourses = 1, prerequisites = []
Output ：[0]

Tips ：

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
all [ai, bi] Different from each other

source ： Power button （LeetCode） link ：https://leetcode.cn/problems/course-schedule-ii
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

My solution to the problem

The words of this question , There was a very similar topic before , At that time, the most obvious difference I remember from this problem should be the size of the data , After all, if you can know whether you can have the whole class, you can basically output the order of classes .

So before, I used a map That's enough , Record the number and depth of these points , Then on this topology （ You can imagine ） Conduct BFS When , Every class I take , I will traverse once prerequisites, Match the post item to the class in map In degree -1, In this way... Can be achieved .

However, such a treatment will not work here , The problem is that the data scale increases , Now it is definitely not possible to cycle through this prerequisites Of , In that case, the time pressure will be greater . So I decided to use a reverse hash table , I take the class that needs to be taught in advance as the second map Of key, Take the course that requires the previous course to be taught normally as a vector Set . In this way, you can directly access the required access every time -1 The point of , It can effectively reduce time .（ Even so, I just got stuck ..）

A final reminder , If I do this because of the ring , Can't finish all classes , It will also output the classes that can be taught , So I still need to set a final judgment condition , The length is not right , It means that you can't go to class , You have to return an empty vector.

Implementation code

class Solution {
    
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    
        map<int,int> ke;
        map<int,vector<int>> re;
        set<int> jihe;
        int l=prerequisites.size();

        for(int i=0;i<numCourses;i++){
    
            ke.insert(pair<int,int>(i,0));
        }

        // here re What the set needs to do is to hang the pre relationship upside down , That is, we need to know that after a class , Which classes have been unsealed , and ke What the collection needs to do is to record the penetration of each course 
        for(int i=0;i<l;i++){
    

            ke[prerequisites[i][0]]++;


            if(re.find(prerequisites[i][1])==re.end()){
    
                vector<int> mid;
                mid.push_back(prerequisites[i][0]);
                re.insert(pair<int,vector<int>>(prerequisites[i][1],mid));
            }
            else{
    
                re[prerequisites[i][1]].push_back(prerequisites[i][0]);
            }
        }
        queue<int> link;
        for(int i=0;i<numCourses;i++){
    
            if(ke[i]==0){
    
                link.push(i);
                jihe.insert(i);
            }
        }
        vector<int> ans,wrong;
        while(!link.empty()){
    
            int num=link.front();
            link.pop();
            ans.push_back(num);
            for(int i=0;i<re[num].size();i++){
    
                int needjian=re[num][i];
                ke[needjian]--;
            }
            for(int i=0;i<numCourses;i++){
    
                if(ke[i]==0&&jihe.find(i)==jihe.end()){
    
                    link.push(i);
                    jihe.insert(i);
                }
            }
        }
        if(ans.size()!=numCourses){
    
            return wrong;
        }
        return ans;
    }
};