拓扑排序可以用到的场景

求基环树中环的大小

在基环树中进行拓扑排序，由于基环树中存在环，所有的点必然不可能都进入拓扑序列，在前面进行拓扑排序的过程中已经将从入度为0的点延申出来的边删完了，没进入拓扑序列中的点每个点的入度必然为2，成为一个环。可以先统计基环树中点的数量，每个点入队的时候就将数量-1，最后剩下来的点就是基环树中环的大小。
P10693 [SNCPC2024] 换座位

 #include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10, M = 5e5+10;
int h[N], e[M], ne[M], idx;
int pos[N], p[N], d[N];
int n, ans;
bool st[N];
vector<int> vec;
int bcnt;//连通块的个数
int id[N];//每个点连通块的编号
vector<int> block[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int x)
{
    int res = 0;
    st[x] = 1;
    for(int i=h[x]; i!=-1; i=ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            res = max(res, dfs(j)+1);
        }
    }
    return res;
}

void dfs1(int x, int bid)
{
    id[x] = bid;
    block[bid].push_back(x);
    for(int i=h[x]; i!=-1; i=ne[i])
    {
        int j = e[i];
        if(!id[j]) dfs1(j, bid);
    }
}

int topsort(int x, int cnt)
{
    queue<int> q;
    for(auto it : block[x])
        if(!d[it])
        {
            q.push(it);
            cnt--;
        }
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        d[p[t]]--;//将出边删除
        if(!d[p[t]])
        {
            q.push(p[t]);
            cnt--;
        }
    }
    return cnt;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        int t;
        cin >> t;
        pos[i] = t;
        add(i, t), add(t, i);
        if(t > n) vec.push_back(t);
    }

    for(auto it : vec)
    {
        if(!st[it])
            ans += dfs(it);
    }
//  cout << ans << endl;
    vec.clear();
    memset(h, -1, sizeof h);
    idx = 0;
    for(int i=1; i<=n; i++)
    {
        int t = pos[i];
        if(st[t]) continue;
        vec.push_back(i);
        p[i] = t;//单向边
        d[t]++;//入度加1
        add(i, t), add(t, i);//建立无向边
        // if(i == t)
        // {
            // ans++;
            // st[i] = 1;
        // }
    }
    for(int i=1; i<=n; i++)
    {
        if(st[i]) continue;//若已经走过则continue
        if(!id[i])//当前节点所在的连通块没有被标记
            dfs1(i, ++bcnt);

    }

    //拓扑排序每个连通块，连通块中剩下的点就是环的大小
    for(int i=1; i<=bcnt; i++)
        ans += topsort(i, block[i].size());


    // for(auto it : vec)
    // {
        // if(st[it]) continue;
        // int cnt = 0;
        // if(dfs1(it, cnt) == it)
            // ans += cnt;
    // }

    cout << ans;
}

求DAG中的最短路

在有向无环图(DAG)上,由于可能存在负权边，dijkstra算法肯定是不能使用了，用spfa和Floyd的话时间复杂度可能会过高。

简单来说就是按拓扑排序的顺序来“松弛”每个结点的最短路径，就是通过入度为0的结点去更新他的邻接点距离源点的最短路径与入度，更新完之后再从入度为0的结点里去更新…这样求最短路的时间复杂度缩小到了O(V+E)，相当于把图遍历一遍就求出来了最短路径，非常高效

AcWing 342. 道路与航线

在对于每个连通块内用dijkstra，连通块间为DAG故可以用拓扑排序求被负权边连着的俩个点的最短路，若一个点能入队，则说明该点的所有前驱节点都已经被考虑过了，根据三角不等式得出来的最终结果即为到该点的最短路
打卡代码