Graph #
- luogu3916 建反向图，深度优先，练习使用 链式前向星。
- uva11175 使用邻接矩阵，题目分析较难想到。
- uva572 深度优先查找连通分量个数。
- uva1599 双重BFS，在最短路径前提下，找最小的序列。较难。
- poj2488 马走遍棋盘的问题，要按字典序做DFS。
- poj3278 同一直线上追逐问题，练习DFS的好例子。
最短路径 #
- luogu4779 单源最短路径模板题，练习Dijkstra算法。
- bailian1797(Heavy Transportation) Dijkstra算法，更新条件稍做变形。dist数组的初始值设置需要留意。
- bailian1860(Currency Exchange) Bellman Ford算法判断正环，需要自定义松驰运算。
- poj3259(Wormholes) SPFA判断负环的存在。
- poj3268 两次SPFA算法，转换视角，构造逆向图。
- P9751([CSP-J 2023] 旅游巴士) 分层图，Djkstra算法。仔细分析题意，这是一个有环图。每个节点会有多个状态。
- P9751([CSP-J 2023] 旅游巴士) 用BFS和二分查找来实现。需要估计最大值搜索的的范围。
最小生成树 #
- luogu3366(【模板】最小生成树) 用链式前向星存图，复用Edge，使用用priority_queue，实现Prim算法。
- bailian1251(Jungle Roads) Prim算法模板题，不需要记录生成树，代码可简化。
- bailian1287(Networking) 并查集优化的Kruskal算法。
- bailian2031(Building a Space Station) Prim算法，建图需要分析。
- bailian2421(Constructing Roads) Prim算法，将已经建好的路的权值设为0。
拓扑排序 #
- bailian2367(Genealogical tree) 拓扑排序模板题，使用邻接矩阵。
- bailian1094(Sorting It All Out) 拓扑排序中判断环，是否唯一，逻辑容易出错。不唯一判断的优先级在环的判断之后。
- poj3687(Labeling Balls) 建反向图，计算节点的入度，与拓扑排序算法的思想一致，但具体做法有区别。
- bailian1270(Following Orders) 用DFS找出所有拓扑序列，节点入度为0，是算法的关键。
- hdu4109(Instrction Arrangement) CPU最短运行时间求的是最长距离。
- poj1949(Chores) 依赖性有次序，无需拓扑排序即可解决。
图的连通性 #
- bailian1144(电话网络) Tarjan算法求割点个数。
- bailian3091(Road Construction) Tarjan算法求解双连通分量，并统计叶子节点个数。需要推导。从题意分析，从任意节点出发，都能访问到其余所有节点，因此，tarjan算法只需执行一次，得到的low数组的值即可视为双连通分量的编号。
- bailian2553(The Bottom of a Graph) Tarjan算法求强连通分量，并输出出度为0的强连通分量的节点。 low值本身并不是用来区分不同强连通分量的。在一个图中，不同强连通分量中的顶点可能会有相同的low值，特别是当不同强连通分量之间存在指向关系时。low值不能作为强连通分量的唯一标识，因为它们只反映了顶点能够回溯到的最早时间戳，而不是顶点属于哪个强连通分量。不能以empty是否为空来判断强连通分量是否结束。
- bailian1236(Network of Schools) Tarjan算法求强连通分量，找到出度为0及入度为0的强连通分量的节点个数。解法与bailian2553相似。