526互联

简单的拓扑排序

发布时间 2023-09-15 10:50:13作者: zhywyt

[OI WiKi]什么是拓扑排序?
简单来说，拓扑排序要解决的问题是给一个有向无环图的所有节点排序。
使用一个队列维护入度为零的节点，取出队列中的节点，存入答案，并把该节点的后续节点入度减一，得到新的有向图。

例题一 ： 标准拓扑

课程表II

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>>g(numCourses);
        vector<int>indgree(numCourses,0);
        for(auto&i:prerequisites){
            g[i[1]].push_back(i[0]);
            indgree[i[0]]++;
        }
        queue<int>q;
        for(int i=0;i<numCourses;i++){
            if(indgree[i]==0){
                q.push(i);
            }
        }
        vector<int>ans;
        while(!q.empty()){
            int i=q.front();
            q.pop();
            ans.push_back(i);
            for(int j:g[i]){
                if(--indgree[j]==0){
                    q.push(j);
                }
            }
        }
        return ans.size()==numCourses?ans:vector<int>();
    }
};

例题二 ： 拓扑+贪心

课程表III

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        //按ddl排序
        sort(courses.begin(),courses.end(),[](const auto&a1,const auto&a2){
            return a1[1]<a2[1];
        });
        priority_queue<int>q;
        int total=0;
        for(const auto& cour:courses){
            int ti=cour[0],ddl=cour[1];
            if(total+ti<=ddl){
                //可以加入,直接加
                total+=ti;
                q.push(ti);
            }
            else if(!q.empty()&&q.top()>ti){
                //有安排的情况下，最后安排的事情耗时大于当前事件
                total-=q.top()-ti;
                q.pop();
                q.push(ti);
            }
        }
        return q.size();
    }
};

例题三 ： 拓扑 + 搜索

课程表IV


class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<int> >g(numCourses);
        vector<int>indgree(numCourses,0);
        vector<vector<bool> >isPre(numCourses,vector<bool>(numCourses,false));
        for(auto&p:prerequisites){
            indgree[p[1]]++;
            g[p[0]].push_back(p[1]);
        }
        queue<int>q;
        for(int i=0;i<numCourses;i++){
            if(indgree[i]==0){
                q.push(i);
            }
        }
        while(!q.empty()){
            auto cur=q.front();
            q.pop();
            //cur的出口
            for(auto&out :g[cur]){
                isPre[cur][out]=true;
                //父节点传递
                for(int i=0;i<numCourses;i++){
                    isPre[i][out]=isPre[i][out] | isPre[i][cur];
                }
                --indgree[out];
                if(indgree[out]==0)q.push(out);
            }
        }
        vector<bool>ans;
        for(auto&que:queries){
            ans.push_back(isPre[que[0]][que[1]]);
        }
        return ans;
    }
};