第5章笔记：图的表示、遍历与有向无环结构

目标

把状态空间变成顶点和边，用遍历不变量覆盖且不重复。

七课依赖

• 邻接表与图输入契约：围绕邻接表与图输入契约先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• DFS、时间戳与边分类：围绕DFS、时间戳与边分类先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• BFS分层与最短步数：围绕BFS分层与最短步数先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 连通分量与染色：围绕连通分量与染色先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 二分图与奇环证据：围绕二分图与奇环证据先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 拓扑排序与入度不变量：围绕拓扑排序与入度不变量先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 强连通分量入口：围绕强连通分量入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复杂度与适用条件表

算法对象	不变量/复杂度来源	使用边界
邻接表与图输入契约	围绕邻接表与图输入契约先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
DFS、时间戳与边分类	围绕DFS、时间戳与边分类先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
BFS分层与最短步数	围绕BFS分层与最短步数先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
连通分量与染色	围绕连通分量与染色先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
二分图与奇环证据	围绕二分图与奇环证据先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
拓扑排序与入度不变量	围绕拓扑排序与入度不变量先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
强连通分量入口	围绕强连通分量入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	BFS只保证单位边权最短路；拓扑序只存在于DAG。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复盘

每题保存暴力、优化、证明、四组边界测试和首个WA输入；一周后换数据重做。