竞赛算法与算法训练 · 小纸条

选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。

第 1 页 · 正面（题目）

1邻接表与图输入契约

闭卷重建邻接表与图输入契约的对象、状态、事件、不变量与一个失败反例。

2DFS、时间戳与边分类

闭卷重建DFS、时间戳与边分类的对象、状态、事件、不变量与一个失败反例。

3BFS分层与最短步数

闭卷重建BFS分层与最短步数的对象、状态、事件、不变量与一个失败反例。

4连通分量与染色

闭卷重建连通分量与染色的对象、状态、事件、不变量与一个失败反例。

5二分图与奇环证据

闭卷重建二分图与奇环证据的对象、状态、事件、不变量与一个失败反例。

6拓扑排序与入度不变量

闭卷重建拓扑排序与入度不变量的对象、状态、事件、不变量与一个失败反例。

7强连通分量入口

闭卷重建强连通分量入口的对象、状态、事件、不变量与一个失败反例。

第 1 页 · 背面（答案）

核心机制：围绕DFS、时间戳与边分类先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成DFS、时间戳与边分类的暴力、优化、对拍与复盘；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕邻接表与图输入契约先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成邻接表与图输入契约的暴力、优化、对拍与复盘；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕连通分量与染色先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成连通分量与染色的暴力、优化、对拍与复盘；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕BFS分层与最短步数先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成BFS分层与最短步数的暴力、优化、对拍与复盘；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕拓扑排序与入度不变量先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成拓扑排序与入度不变量的暴力、优化、对拍与复盘；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕二分图与奇环证据先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成二分图与奇环证据的暴力、优化、对拍与复盘；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕强连通分量入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成强连通分量入口的暴力、优化、对拍与复盘；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。本课必须再检查边界输入、整数溢出、下标和不可行状态。。