经典模板汇总 - 提高组图论

过了这些题，加深你对图论的理解！

图论的经典模板题，包括：

图的表示与遍历
并查集
最短路径
负环
生成树
拓扑排序与关键路径
欧拉回路与哈密顿回路
强连通分量
割点和桥
点双连通分量和边双联通分量
二分图匹配

不断更新ing

注意：有些算法的模板题洛谷没有，只能选择了一些经典题目当作模板题。如果你有更好的题目，欢迎私信本蒟蒻！

我的其它题单

ois 的普及算法训练计划

现将题目列表写在下面（加粗的为我人为加的标记，不属于原题题名）：

图的表示与遍历

B3600 [图论与代数结构 101] 图的代数表示 （图的代数表示）
P1692 部落卫队 （图的深度优先遍历）
Floyd
P2910 [USACO08OPEN]Clear And Present Danger S （Floyd 最短路）
P6175 无向图的最小环 （Floyd 最小环）
并查集

（虽然不是图论，但是作为 Kruskal 的基础这里也放上了）
P3367 【模板】并查集 （路径压缩并查集）
P1892 [BOI2003]团伙 （反集）
P2024 [NOI2001]食物链 （扩展域并查集，种类并查集）
单源最短路径
P3371 【模板】单源最短路径（弱化版）（不优化的 Dijkstra，Bellman-Ford，SPFA）
P4779 【模板】单源最短路径（标准版） （堆优化 Dijkstra）
负环
P3385 【模板】负环
最小生成树
P3366 【模板】最小生成树 （Kruskal）
拓扑排序、关键路径

欧拉回路、哈密顿回路
P7771 【模板】欧拉路径
强连通分量
B3609 [图论与代数结构 701] 强连通分量 （Kosaraju，Tarjan）
割点和桥
P3388 【模板】割点（割顶）（Tarjan）
二分图匹配
P3386 【模板】二分图最大匹配 （匈牙利算法）