有向无环图
有向无环图是一种特殊的图，其最大的意义在于能够拓扑排序。
拓扑排序是指给这个图的 \(n\) 个点排序，使得所有 \(x \rightarrow y\) 的边 \(x\) 点都在 \(y\) 前面。
求最短路是 \(O_{(n + m)}\) 的，也可以在这张图上做 DP。
拓扑排序
考虑维护一个入度为 \(0\) 的点的集合。
因为这些点之间没有依赖关系，我们可以将它放在序列的开头，所有依赖它的点都在它的后面。
放在开头后删掉它，更新剩余入度为 \(0\) 的点，继续这个过程。
强联通分量
称一个有向图强连通是指，图里的任意两点都连通。
强连通分量就是一个极大的强连通子图。
DFS 生成树。
求强连通分量
强连通分量最大的作用是缩点，变成一个 DAG。
双连通分量
无向图有两种不同的连通分量，一种是点双连通，一种是边双连通，即存在两条不经过重复点/边的路径。
点双不具有传递性，边双具有传递性。
割点和割边 求割点的办法和有向图基本类似，需要特判根只有一个儿子的情况，割边也差不多。
一般只有边双需要缩点，也和有向图类似。
求割边割点