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

**过了这些题，加深你对图论的理解！** 图论的经典模板题，包括： - 图的表示与遍历 - 并查集 - 最短路径 - 负环 - 生成树 - 拓扑排序与关键路径 - 欧拉回路与哈密顿回路 - 强连通分量 - 割点和桥 - 点双连通分量和边双联通分量 - 二分图匹配 不断更新ing 注意：有些算法的模板题洛谷没有，只能选择了一些经典题目当作模板题。如果你有更好的题目，欢迎私信本蒟蒻！ **** **我的其它题单** [ois 的普及算法训练计划](https://www.luogu.com.cn/training/3322) **** 现将题目列表写在下面（**加粗**的为我人为加的标记，不属于原题题名）： ## 图的表示与遍历 - B3600 [图论与代数结构 101] 图的代数表示 **（图的代数表示）** - P1692 部落卫队 **（图的深度优先遍历）** ## Floyd - P2910 [USACO08OPEN]Clear And Present Danger S **（Floyd 最短路）** - P6175 无向图的最小环 **（Floyd 最小环）** ## 并查集 **（虽然不是图论，但是作为 Kruskal 的基础这里也放上了）** - P3367 【模板】并查集 **（路径压缩并查集）** - P1892 [BOI2003]团伙 **（[反集](https://www.luogu.com.cn/blog/180720/note-union-search-set-more)）** - P2024 [NOI2001]食物链 **（扩展域并查集，种类并查集）** ## 单源最短路径 - P3371 【模板】单源最短路径（弱化版）**（不优化的 Dijkstra，Bellman-Ford，SPFA）** - P4779 【模板】单源最短路径（标准版） **（堆优化 Dijkstra）** ## 负环 - P3385 【模板】负环 ## 最小生成树 - P3366 【模板】最小生成树 **（Kruskal）** ## 拓扑排序、关键路径 ## 欧拉回路、哈密顿回路 - P7771 【模板】欧拉路径 ## 强连通分量 - B3609 [图论与代数结构 701] 强连通分量 **（Kosaraju，Tarjan）** ## 割点和桥 - P3388 【模板】割点（割顶）**（Tarjan）** ## 二分图匹配 - P3386 【模板】二分图最大匹配 **（匈牙利算法）**