图论入门题
图论简介：
图（Graph）
图可以被表示为 G={V, E}，其中 V={v1, ... , vN}表示n个点，E= {e1, ... , eM}表示m条边。
常用的储存方式包括邻接表和邻接矩阵。
连通分量（Connected Component）：各节点间至少存在一条边可以连通。
图的最短路入门：
P1144 最短路计数
B3647 【模板】Floyd 算法
P2910 [USACO08OPEN] Clear And Present Danger S
B3611 【模板】传递闭包
拓扑排序入门：
B3644 【模板】拓扑排序 / 家谱树
P3074 [USACO13FEB] Milk Scheduling S
最短路算法
Floyd算法与前两种算法不同，它是求解顶点之间两两最短距离。其基本思想是，如果节点i.k的距离加上k,j的距离小于i,j的距离，则更新i,j的距离。该思想与动态规划的思想类似。需要注意的是，在枚举的过程中，需要先枚举k，再枚举ij。Floyed算法时间复杂度为O(N3)。虽然该复杂度与枚举起始节点的Dijkstra算法一致，但是Floyed算法常数复杂度比Dijkstra小很多。
拓补排序：
拓扑排序是对一个有向图构造拓扑序列，解决工程是否能顺利进行的问题。构造时有 2 种结果：
- 此图全部顶点被输出：说明说明图中无「环」存在， 是 AOV 网
- 没有输出全部顶点：说明图中有「环」存在，不是 AOV 网
AOV（Activity On Vertex Network） ：一种 有向 无回路 的图。
求解方法：每次删除一个入度边个数为 0 的点，并刷新其他点的出度边个数