洛谷题单:图的遍历、拓扑排序、欧拉路径等【普及-提高】
作者:
along1083
,
2025-04-11 10:33:07
· 广东
,
所有人可见
,
阅读 3
洛谷图论题单(普及-到提高难度)
一、图的遍历
题目编号 |
题目名称 |
关键点 |
难度 |
链接 |
P5318 |
【深基18.例3】查找文献 |
邻接表排序,DFS/BFS遍历 |
普及- |
题目 |
P3916 |
图的遍历 |
反向建图,倒序DFS |
普及/提高- |
题目 |
P1605 |
迷宫 |
回溯法求路径数 |
普及- |
题目 |
P1141 |
01迷宫 |
连通块预处理,记忆化搜索 |
普及/提高- |
题目 |
二、拓扑排序
题目编号 |
题目名称 |
关键点 |
难度 |
链接 |
B3644 |
【模板】拓扑排序/家谱树 |
基础拓扑序,队列实现 |
普及- |
题目 |
P4017 |
最大食物链计数 |
拓扑排序+DP统计路径 |
普及+/提高- |
题目 |
P1137 |
旅行计划 |
拓扑序递推最长路 |
普及+/提高- |
题目 |
P1038 |
[NOIP2003]神经网络 |
拓扑排序模拟信号传递 |
普及+/提高- |
题目 |
三、欧拉路径
题目编号 |
题目名称 |
关键点 |
难度 |
链接 |
P7771 |
【模板】欧拉路径 |
有向图字典序最小路径 |
提高- |
题目 |
P1341 |
无序字母对 |
无向图欧拉回路构造 |
普及+/提高- |
题目 |
P2731 |
[USACO]骑马修栅栏 |
邻接矩阵实现欧拉路 |
普及+/提高- |
题目 |
四、综合题单推荐
- 基础拓扑排序合集
- 包含队列实现、DP结合等基础题型
- 图论能力提升Part8
- 覆盖最短路、连通性、拓扑排序等综合训练
- 欧拉路径专题
- 包含有向/无向图的判定与构造方法
注:标*题目建议优先完成,部分题目需结合邻接表优化(如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,环上断边策略 |
提高- |
题目 |
五、推荐题单
- 拓扑排序专题训练
- 包含基础模板与综合应用(如P4017食物链计数)
- 欧拉路径进阶
- 覆盖有向/无向图的判定与构造技巧
- 图论综合能力提升
- 包含最短路、连通性等综合训练(如P2661信息传递)
注:标*题目建议结合题解食用,部分题目需预处理(如P4742的缩点)或特殊技巧(如P3243的反向拓扑)。