【模板】拓扑排序
拓扑排序
拓扑排序是一种适用于有向无环图（简称DAG）中的算法，它拥有较低的复杂度，较简单的代码难度。
什么是有向无环图？
对于一张有向图，倘若一条边的终点无法通过其他路径指向起点，那么这张图就可以称作有向无环图。
拓扑排序在什么时候适用？
首先题目中涉及到的图需要是DAG，同时每个点的状态由指向该点的所有点决定，因此拓扑排序的思路更倾向于动态规划，也常常在动态规划相关章节进行介绍。
拓扑排序算法详解
由于DAG的特性，图中的所有节点中会有一类点比较特殊：这些点没有任何前驱，即没有任何边指向这些点，只有从这个点出发指向其他点的边。我们将这些点称为DAG的起点，同理我们可以得到DAG中终点的定义。
由定义，我们可以得知DAG中的起点（终点）可以有多个，但是不会为零个。起点的状态由题面得知，其余点的状态由所有前驱点共同决定。
我们用队列作为待遍历的点的容器，在最开始将所有起点加入队列，此后每次取出一个点，并且遍历这个点引出的所有边，对其后继点进行更新。当某个点的所有前驱点都遍历过后这个点的状态就已经完全决定了，此时可以将这个点加入队列准备遍历。通过这样的方法可以保证所有点都会进入一次队列，所有边都会被遍历且仅遍历一次。
由于算法中涉及到起点和前驱点，我们在输入边的时候需要统计每个点的入度。这样最初入度为零的点就是起点，此后每次遍历一条边的时候对其终点的入度减一（可以理解为遍历过这条边后就删掉），于是当某个点的入度减小到零后即意味着这个点的状态已经确定，那么将这个点加入队列。
以上就是算法的思路详解，由以上可以得到，DAG中每个点每条边都会被遍历到并且都只会遍历一次，因此拓扑排序的时间复杂度为 \(O(n+m)\) ，是效率很高的算法。
例题 & 代码
题目传送门
//------------------------
//Online Judge : Luogu
//By : KS_tips_CN
//Subject : P4017 最大食物链计数
//------------------------
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#define ll long long
#define reg register int
#define gc getchar()
#define MAXN 5010
#define MAXM 500010
#define MOD 80112002
using namespace std;
inline ll read( void ) ;
int N,M,id[MAXN],od[MAXN],val[MAXN];
vector<int> E[MAXN];
queue<int> Q;
int x,y,HD,TL,sum;
int main( void ) {
N = read();
M = read();
for( reg i = 1 ; i <= M ; i++ ){
x = read();
y = read();
E[y].push_back(x);
//在这里反向连边从生产者指向最高级消费者
id[x]++;
od[y]++;
}
for( reg i = 1 ; i <= N ; i++ )
if( !id[i] ) { val[i] = 1 ; Q.push(i) ; }
while( !Q.empty() ){
HD = Q.front() ;
Q.pop() ;
for( reg i = 0 ; i < E[HD].size() ; i++ ){
TL = E[HD][i]; //取出终点
val[TL] = ( val[TL] + val[HD] ) % MOD ; //更新食物链数量，随时取模
id[TL]--;
if( !id[TL] ) Q.push(TL); //入度为零则进入队列
}
}
for( reg i = 1 ; i <= N ; i++ )
if( !od[i] ) {
//在这里我们只需要考虑终点的食物链数量
sum += val[i];
sum %= MOD;
}
cout << sum << endl ;
return 0;
}
inline ll read( void ) {
ll x = 0 , f = 0 ;
char ch = gc ;
while( !isdigit( ch ) )
f |= ( ch == '-' ) , ch = gc ;
while( isdigit( ch ) )
x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ) , ch = gc ;
return f ? -x : x ;
}
以上就是拓扑排序算法的详解，本人水平有限，若对该算法或代码有不解的地方随时可以提问，欢迎各位提供建议以及指出不足。