图论

最短路 Floyd O(n³) 通过枚举中间点来更新两点间最短路. SPFA(单源) O(nlogn) 维护一个队列，最初只含有起点； 每次取出队头元素x，对于x的所有出边(x,y,z)，若Dis[x]+z<Dis[y]，松弛成功，则更新Dis[y]，将y入队. Dijkstra(单源) O(nlogn) 初始化Dis为INF，起点为0； 找出一个Dis最小且未被标记的节点x并将其标记； 对于x的所有出边(x,y,z)，若Dis[x]+z<Dis[y]，松弛成功，则更新Dis[y]. 最小生成树 Prim Kruskal 次小生成树 树的直径 树形Dp 两次BFS LCA 向上标记 树上倍增 Tarjan 负环与差分约束 SPFA判负环 差分约束系统 Tarjan与无向图的连通性 桥 e-DCC e-DCC缩点 割点 v-DCC v-DCC缩点 欧拉路径 欧拉回路 Tarjan与有向图的连通性 SCC SCC缩点 必经点&必经边 2-SAT 二分图 染色判定 增广路匹配