图论入门题单

图论入门的难点通常是建图，而不是背某个模板。每道题先明确顶点、边、方向和边权，再判断题目问的是连通性、最短路、依赖关系还是连通代价。

一、图的存储与遍历

先掌握邻接表、访问标记和 DFS/BFS 顺序。网格图可以看成特殊的隐式图。

• luogu P5318 【深基18.例3】查找文献题解
  · P5318 【深基18.例3】查找文献
• luogu P3916 图的遍历题解
  · P3916 图的遍历
• luogu P1451洛谷原题
  · P1451 求细胞数量
• luogu P1141洛谷原题
  · P1141 01迷宫
• codeforces 20C未收录
  · Codeforces 20C Dijkstra?

二、连通性与并查集

静态连通块可以 DFS/BFS，边不断加入的连通性则适合并查集。P2024 作为带权并查集挑战题，放在这一节最后。

• hdu 1213未收录
  · HDU 1213 How Many Tables
• luogu P3367 【模板】并查集题解
  · P3367 【模板】并查集
• luogu P1551 亲戚题解
  · P1551 亲戚
• luogu P1955 [NOI2015] 程序自动分析题解
  · P1955 程序自动分析
• luogu P2024 [NOI2001] 食物链题解
  · P2024 食物链

三、最短路

无权图先用 BFS；非负边权使用 Dijkstra。重点是理解“松弛”在维护什么不变量。

• hdu 2544未收录
  · HDU 2544 最短路
• luogu P3371洛谷原题
  · P3371 【模板】单源最短路径（弱化版）
• luogu P4779 【模板】单源最短路径（标准版）题解
  · P4779 【模板】单源最短路径（标准版）
• luogu P1144 最短路计数题解
  · P1144 最短路计数
• luogu P1462 通往奥格瑞玛的道路题解
  · P1462 通往奥格瑞玛的道路

四、拓扑排序与 DAG

入度为零的点代表当前没有未完成的前置依赖。除了排序，还要练习在 DAG 上做最长路或计数 DP。

• luogu P1347 [ECNA 2001] 排序题解
  · P1347 排序
• luogu P4017 最大食物链计数题解
  · P4017 最大食物链计数
• luogu P1113 [USACO02FEB] 杂务题解
  · P1113 杂务
• luogu P1807 最长路题解
  · P1807 最长路

五、最小生成树与二分图

Kruskal 的核心是按边权从小到大尝试合并；二分图染色的核心是判断相邻点能否使用不同颜色。

• luogu P3366 【模板】最小生成树题解
  · P3366 【模板】最小生成树
• luogu P2872 [USACO07DEC] Building Roads S题解
  · P2872 Building Roads S
• luogu P1991 无线通讯网题解
  · P1991 无线通讯网
• luogu P1330 封锁阳光大学题解
  · P1330 封锁阳光大学
• luogu P1525 [NOIP 2010 提高组] 关押罪犯题解
  · P1525 关押罪犯

六、强连通分量挑战

强连通分量是图论入门的收尾内容。先理解 DFS 时间戳和反图，再学习 Tarjan 或 Kosaraju。

• hdu 1269未收录
  · HDU 1269 迷宫城堡
• luogu P3387 【模板】缩点题解
  · P3387 【模板】缩点
• luogu P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G题解
  · P2341 奶牛的仰慕 G

过关标准

1
2
3能根据题意写出顶点、边、方向和边权：
能判断 BFS、Dijkstra、并查集、拓扑排序和 Kruskal 的适用条件：
能说明最短路松弛或并查集合并为什么不会破坏已有结论：