算法提高课第三章拓扑排序_拓扑排序提高-CSDN博客

本文链接：https://blog.csdn.net/csdn_ggboy/article/details/121525462

这两篇博客介绍了拓扑序的概念及其在AcWing题库中的应用，通过C++代码展示了如何求解状态可达性。第一篇博客通过队列实现拓扑排序，计算每个节点的可达状态数；第二篇博客利用虚拟源点解决车站分级问题，通过添加虚拟节点优化路径计算。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

164. 可达性统计 - AcWing题库

求解拓扑序
按照拓扑序求解状态（状态定义为bitset<N>)
AcWing 164. 可达性统计(2种简单写法) - AcWing

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
using namespace std;
const int N = 30010;
const int M = N;
int n, m;
int h[N], e[M], ne[M], idx;
bitset<N> f[N];
int le[N], cnt = 0, ind[N];
void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++ )
    {
        int a, b;
        cin >> a >> b;//a--->b
        add(a, b);
        ind[b] ++;
    }
    queue<int> q;
    for(int i = 1; i <= n; i ++ )
        if(!ind[i]) q.push(i);
    while(q.size())
    {
        int u = q.front();
        q.pop();
        le[++ cnt] = u;
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            ind[j] --;
            if(!ind[j]) q.push(j);
        }
    }
    for(int i = cnt; i >= 1; i -- )
    {
        int u = le[i];
        f[u][u] = 1;//自己可达
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];// u--->j
            f[u] |= f[j];
        }
    }
    for(int i = 1; i <= n; i ++) cout << f[i].count() << endl;
}

456. 车站分级 - AcWing题库

虚拟源点的应用
AcWing 456. 车站分级 - AcWing

//不停靠说明 a < b
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
const int N = 3100;
const int M = 5000100;
int n, m;
int ind[N], dist[N], a[N];
int h[N], e[M], ne[M], idx, w[M];
int cnt1, cnt2;
bool g[N][N];
bool vis[N];
void add(int a, int b, int c)  // 添加一条边a->b
{
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int main()
{
    ios::sync_with_stdio(false);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++ )
    {
        cin >> cnt1;
        memset(vis, 0, sizeof vis);
        cnt2 = 0 ;
        for(int j = 1; j <= cnt1; j ++ )
        {
            cin >> a[j];
            vis[a[j]] = true;
        }
        // j --- > n + 1 ---- > k
        for(int j = a[1]; j <= a[cnt1]; j ++ )
        {
            if(vis[j]) add(n + i, j, 1), ind[j] ++;
            else add(j, n + i, 0), ind[n + i] ++;
        }
    }
    
    queue<int> q;
    for(int i = 1; i <= n; i ++ ) dist[i] = 1;
    for(int i = 1; i <= n + m; i ++ )
    {
        if(!ind[i]) 
        {
            q.push(i);
        }
    }
    while(q.size())
    {
        int u = q.front();
        q.pop();
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            dist[j] = max(dist[j], dist[u] + w[i]);
            ind[j] --;
            if(!ind[j]) q.push(j);
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++ ) ans = max(ans, dist[i]);
    cout << ans;
}