拓扑排序总结

caizimo · 2025-10-06 17:09:52 · 个人记录

拓扑排序总结

拓扑序：

定义：

给定n个点m条边的有向边，将n个点整理成一个序列，使得对于任意一条边i，总有i的出点在i的入店之前，这样的序列称之为图的拓扑序。

性质

1.只有有向无环图（DAG），才有拓扑序。\ 2.同一张图的拓扑序不一定唯一

拓扑排序：

整理拓扑序的算法称为拓扑排序。

拓扑排序的实现

1.统计每个点的入度in[i]\ 2.枚举所有点，并将入度为0的店插入队列（或者栈）\ 3.循环取出队头元素x输出，x指向的所有点y的入读-1，in[y]--；\ 4.当in[y]=0时，将y插入队列。 5.重复步骤3-4，直到队列为空。

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
int n,in[N];
vector<int> g[N];
queue<int> q;
void topo(){
    for(int i=1;i<=n;i++){
        if(in[i]==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int x=q.front();
        cout<<x<<' ';
        q.pop();
        for(int i=0;i<g[x].size();i++){
            int y=g[x][i];
            in[y]--;
            if(in[y]==0) q.push(y);
        }
    }
    return ;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;){
        int x; cin>>x;
        if(x){
            g[i].push_back(x);
            in[x]++;
        }
        else i++;
    }
    topo();
    return 0;
}

常见题型

1.普通拓扑排序（板子）\ 例：B3644\ 2.找环\ 例：P2712\ 3.DP+拓扑\ 例：P1113

时间复杂度