算法综合三：拓扑状态与环检测

来源与归并方式

本课对应来源课程：26考研王道计算机【数据结构冲刺班】。manifest统计该课程共有 530 个JSON。本章只依据文件名中的考点、年份题号、选择/算法/套卷标签做主题归并，不是逐条复制，也未读取转写正文。

本课归并桶：图算法、综合题文件名归并。

冲刺核心

有向图存在拓扑序当且仅当无环。Kahn算法维护入度0队列，处理一个顶点后削减其出边终点入度。

限时训练法

已输出顶点不再参与图；若最终输出数小于n，剩余子图每个顶点入度都大于0，必含有向环。

每题都记录开始时间、首次答案、置信状态和第一处错误。选择题要写排除依据；算法题要写契约、不变量与复杂度。

本课应用

输入n m及m条有向边u v（0下标），若图有环输出1，否则输出0。

严格验收

• 必须做到：重复边若被题目允许，应按实际边数维护入度并逐边删除。
• 高频陷阱：DFS或Kahn未访问完时可直接把图判为不连通，而不是有环。

完成后隔一天用同类不同题复测。只看解析、不遮答重做，不计入掌握。