拓扑排序的英文名是 Topological sorting。
拓扑排序要解决的问题是给一个图的所有节点排序。
拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。 ——OI-WiKi
拓扑排序是在 DAG（有向无环图） 中每次选则入度为 0 的节点加入队列，并删除与这个节点相连的边，重复执行此操作。
这样做的作用是后面加入队列的节点一定不依赖于前面的节点，因此拓扑排序有无后效性，可以用于 dp。
也可以用于判环，当队列为空时若还有边则该图有环。
例题 1：
思路很简单， d[] 用于存储最长距离， rd[] 用于存储入度。
第一遍代码：
#include
#include
#include
using namespace std;
const int N = 1505;
int n, m;
int u, v, w;
int t;
long long d[N];
bool f[N][N];
int g[N][N];
int rd[N];
queue q;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i
45 分，下了一组数据，发现有重边的情况。。。。
略改输入部分代码。
#include
#include
#include
using namespace std;
const int N = 1505;
int n, m;
int u, v, w;
int t;
long long d[N];
bool f[N][N];
int g[N][N];
int rd[N];
queue q;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i
然并卵，还是 WA。
原因是其他与目标路径无关的点没有入队，导致部分点最长路已经确定了，但入度不为 0，解决方法就是在 1 入队之前先把其他入度为 0 的点入队，A 之。
最终代码：
#include
#include
#include
using namespace std;
const int N = 1505;
int n, m;
int u, v, w;
int t;
long long d[N];
bool f[N][N];
int g[N][N];
int rd[N];
queue q;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i
其实可以跑 SPAF
例题 2：
类似板子题，一开始只需要将所有入度为 0 的点入队，没有奇怪数据。
代码：
#include
#include
#include
#include
using namespace std;
const int N = 1e5 + 10;
int n, m, x, y, t;
int rd[N], d[N];
vector g[N];
queue q;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i
总结：
Original: https://www.cnblogs.com/cjwen6/p/15878687.html
Author: cjwen6
Title: 「周记」拓扑排序
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/712989/
转载文章受原作者版权保护。转载请注明原作者出处！