总论:
拓扑图是有向无环图,且具有拓扑序,但是不一定是树,而树一定是拓扑图。
不能用树的 dfs 的方式去搜索拓扑图,除非这个拓扑图是树。
下面的 T5 我开始不知道这点,用的树的 dfs WA 了好几次,然后猛然意识
到拓扑图不一定是树但树一定是拓扑图。
1.判断一个图具不具有拓扑序/是不是拓扑图
判断一个图是不是拓扑图,可以对其进行一次拓扑排序,是拓扑图则
入队的点一定是 n 个,否则会因为存在环而使得有些点入度总是不为
0,从而不能入队,使得入队的点少于 n 个
AcWing 848. 有向图的拓扑序列
2.给出 k 次询问,问哪些序列不是可以由图得到的拓扑序列
Acwing 1639. 拓扑顺序
3.询问在一个拓扑图里面一个点能达到多少个点,用到了 bitset
这题时间复杂度我不知道多少
Acwing 164. 可达性统计
4.用到了入度和出度的拓扑排序题
Acwing 477. 神经网络
5.用到了 dp 求拓扑图路径的最大值
Acwing 1011. 挖地雷
6.输出一个拓扑图的任意一个拓扑序列
AcWing 1191. 家谱树
7.拓扑排序求最小路径和
1192. 奖金