拓扑排序

简介

拓扑排序是指，在有向无环图(DAG)中，总有节点A指向节点B的这一关系，这可以理解为节点A的优先级高于节点B。而拓扑排序需要的就是把节点按优先级排序。

这需要用到两个概念：出度和入度。出度即节点A指向多少个节点，入度即节点A被多少个节点所指。显然，出度为0时，优先级最低，入度为0时优先级最高

那么如何输出一个拓扑排序呢？只需要我们找到所有入度为0的点，将其输出，再继续输出其下层的点，重复此步骤即可，这是天然符合BFS的。

接下来让我们看看用BFS和DFS实现拓扑排序的方法。

P1113 杂务

这个题可以通过DFS加记忆化搜索去做，即完成一项任务的最小时间取决于其所有前驱中花费时间的最大值，在图论基础中有涉及。

但此题也可通过先获得拓扑序，对拓扑序分层后使用动态规划求解

在此提供BFS+DP的代码，需要注意两个点。

其一是拓扑排序的只会把入度为0的点入队。除去一开始为0的点，只有入度被改变的点才可能为0，所以不需要重新检查一次

其二是需要有dp检查最大值，因此问题是一个最长路问题，需要用dp去储存当访问到此处时的最长路劲。

#include <iostream>
#include <vector>
#include<deque>
#include <algorithm>
using namespace std;
const int MAXN = 1e4+5;
int n;
vector<int> a[MAXN];
int times[MAXN],dp[MAXN],rudu[MAXN];
int res=0;
deque<int> q;
void func(){
    q.clear();
    for(int i=1;i<=n;i++){
        if(rudu[i]==0){ 
            q.push_back(i);
            dp[i] = times[i]; 
        }
    }
    while(q.size()){
        int nowIndex = q.front();
        q.pop_front();
        for(int i=0;i<a[nowIndex].size();i++){
            int t = a[nowIndex][i];//a的邻居
            rudu[t]--;
            if(rudu[t]==0) q.push_back(t);
            dp[t] = max(dp[t],dp[nowIndex]+times[t]);
        }
        res = max(dp[nowIndex],res);
    }
}
int main() {

    cin>>n;
    for(int i=1;i<=n;i++){
        int a1,b,c;cin>>a1>>b>>c;
        times[i]=b;
        while(c!=0){
            rudu[i]++;
            a[c].push_back(i);
            cin>>c;
        }
    }
    func();
    cout<<res;
    return 0;
}