拓扑排序（一部分）

DAG有向无环图又被称为拓扑图，拓扑序列指的是将每个节点能按照起点到终点的顺序排列。

例一：活动 - AcWing

板子题，入度 | 出度

#include 
#include 
#include 
using namespace std;
 
const int N = 1e5 + 10;
int n, m;
int e[N], ne[N], h[N], idx;
int d[N]; // 表示入度
queue<int> q, ans;
 
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
 
bool topsort() // 其实就是bfs
{
    for(int i = 1; i <= n; i ++ )
    {
        if(!d[i])
        {
            q.push(i);
        }
    }
    
    while(q.size())
    {
        int t = q.front();
        ans.push(t);
        q.pop();
        
        for(int i = h[t]; i != -1; i = ne[i]) // 遍历入度为0后的每一个点，寻找下一个入度=0
        {
            int j = e[i];
            d[j] --;
            if(!d[j]) q.push(j);
        }
    }
    
    return ans.size() == n;
}
 
int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    while(m -- )
    {
        int a, b;
        cin >> a >> b;
        
        add(a, b);
        d[b] ++;
    }
    
    if(topsort()) // 存在拓扑序列
    {
        while(ans.size())
        {
            cout << ans.front() << ' ';
            ans.pop();
        }
    }
    else
    {
        puts("-1");
    }
 
    return 0;
}

例二：P1113 杂务 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这题得到了一个拓扑序之后，能够算出同时进行的多个杂物所需时间，用a去记忆答案

#include 
#include 
#include 
 
using namespace std;
 
const int N = 1e4 + 10;
int n;
vector<int> e[N]; // 邻接表
int ans, a[N], len[N];
int d[N];
queue<int> q;
 
void topsort()
{
    for(int i = 1;i <= n; i ++ )
    {
        if(!d[i])
        {
            q.push(i);
            a[i] = len[i];
        }
    }
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        for(int i = 0; i < e[t].size(); i ++ )
        {
            int j = e[t][i];
            d[j] --;
            if(!d[j])
            {
                q.push(j);
            }
            a[j] = max(a[j], a[t] + len[j]); // 并行的杂务算出最大覆盖的时间
        }
    }
}
 
int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i ++ )
    {
        int a, b;
        cin >> a;
        cin >> len[a];
        
        while(scanf("%d", &b))
        {
            if(!b) break;
            e[b].push_back(a);
            d[a] ++;
        }
    }
    
    topsort();
    
    for(int i = 1; i <= n; i ++ )
    {
        ans = max(a[i], ans);
    }
    
    cout << ans << endl;
    return 0;
}

例三：P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

也是记忆化+拓扑

#include 
#include 
#include 
 
using namespace std;
 
const int N = 5010;
struct edges
{
    int a, b, w;
};
vector e[N];
int n, m;
int ind[N];
queue<int> q;
int f[N];
bool st[N];
 
void toposort()
{
    for(int i = 1; i <= n; i ++ )
    {
        if(!ind[i]) 
        {
            q.push(i);
        }
    }
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        for(int i = 0; i < e[t].size(); i ++ )
        {
            int j = e[t][i].b;
            ind[j] --;
            if(!ind[j])
            {
                q.push(j);
            }
            if(st[t])
            {
                st[j] = true;
                f[j] = max(f[j], f[t] + e[t][i].w);
            }
        }
    }
}
 
int main()
{
    cin >> n >> m;
 
    for(int i = 0; i < m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        
        e[a].push_back((edges){a, b, w});
        ind[b] ++;
    }
 
    st[1] = true;
    f[n] = -1; // 如果说无法到达 就输出-1
 
    toposort();
    
    cout << f[n] << endl;
    return 0;
}

toposort的应用还有很多，比如说在动态规划中，但是我还没学