洛谷题单：图的遍历、拓扑排序、欧拉路径等【普及-提高】

作者： 作者的头像   along1083 ,  2025-04-11 10:33:07 · 广东 ,  所有人可见 ,  阅读 7

0


洛谷图论题单（普及-到提高难度）

一、图的遍历

题目编号 题目名称 关键点 难度 链接
P5318 【深基18.例3】查找文献 邻接表排序，DFS/BFS遍历 普及- 题目
P3916 图的遍历 反向建图，倒序DFS 普及/提高- 题目
P1605 迷宫 回溯法求路径数 普及- 题目
P1141 01迷宫 连通块预处理，记忆化搜索 普及/提高- 题目

二、拓扑排序

题目编号 题目名称 关键点 难度 链接
B3644 【模板】拓扑排序/家谱树 基础拓扑序，队列实现 普及- 题目
P4017 最大食物链计数 拓扑排序+DP统计路径 普及+/提高- 题目
P1137 旅行计划 拓扑序递推最长路 普及+/提高- 题目
P1038 [NOIP2003]神经网络 拓扑排序模拟信号传递 普及+/提高- 题目

三、欧拉路径

题目编号 题目名称 关键点 难度 链接
P7771 【模板】欧拉路径 有向图字典序最小路径 提高- 题目
P1341 无序字母对 无向图欧拉回路构造 普及+/提高- 题目
P2731 [USACO]骑马修栅栏 邻接矩阵实现欧拉路 普及+/提高- 题目

四、综合题单推荐

  1. 基础拓扑排序合集
  2. 包含队列实现、DP结合等基础题型
  3. 图论能力提升Part8
  4. 覆盖最短路、连通性、拓扑排序等综合训练
  5. 欧拉路径专题
  6. 包含有向/无向图的判定与构造方法

注：标*题目建议优先完成，部分题目需结合邻接表优化（如P7771）或特殊处理（如P1341的字符映射）。

洛谷图论进阶题单（普及-到提高难度）

一、图的遍历与连通性

题目编号 题目名称 关键点 难度 链接
P2661 信息传递 最小环检测，DFS/BFS/并查集 普及+/提高- 题目
P2921 [USACO08DEC]农场派对 基环树遍历，反向建图 普及+/提高- 题目
P3623 [APIO2008]免费道路 生成树+DFS验证连通性 提高- 题目

二、拓扑排序进阶

题目编号 题目名称 关键点 难度 链接
P2712 摄像头 拓扑排序删点，贪心策略 普及+/提高- 题目
P3243 [HNOI2015]菜肴制作 拓扑序字典序反向处理 提高- 题目
P4742 [Wind Festival]Running In The Sky 拓扑排序+强连通分量缩点 提高 题目

三、欧拉路径变形

题目编号 题目名称 关键点 难度 链接
P3520 [POI2011]SMI-Garbage 无向图欧拉回路构造 提高- 题目
P6066 Watchcow S 有向图欧拉回路，边遍历顺序控制 普及+/提高- 题目

四、综合应用

题目编号 题目名称 关键点 难度 链接
P4630 [APIO2018]铁人两项 圆方树+DFS统计路径 提高 题目
P5022 [NOIP2018]旅行 基环树DFS，环上断边策略 提高- 题目

五、推荐题单

  1. 拓扑排序专题训练
  2. 包含基础模板与综合应用（如P4017食物链计数）
  3. 欧拉路径进阶
  4. 覆盖有向/无向图的判定与构造技巧
  5. 图论综合能力提升
  6. 包含最短路、连通性等综合训练（如P2661信息传递）

注：标*题目建议结合题解食用，部分题目需预处理（如P4742的缩点）或特殊技巧（如P3243的反向拓扑）。

0 评论

1024
x