地图中有些走廊存在替代路线,另一些则承担唯一连接。检查哪条走廊不能断开,关注的是边的失效,与删除整个房间及其全部通道的分析不同。
明确本例规则
本例使用连通的无向简单图。深度遍历时记录发现时刻,以及通过子树和至多一条回边能达到的最早发现时刻。树边从父房间u指向子房间v时,若v的最早可达时刻严格大于u的发现时刻,这条边就是桥。
输入与逐步结果
九个房间,走廊列表[(0, 1), (0, 2), (0, 3), (1, 4), (1, 5), (2, 6), (4, 7), (4, 8)];从零开始按邻居编号遍历。
房间 | 发现时刻 | 最早可达时刻 0 | 0 | 0 1 | 1 | 1 2 | 6 | 6 3 | 8 | 8 4 | 2 | 2 5 | 5 | 5 6 | 7 | 7 7 | 3 | 3 8 | 4 | 4 断开会分裂地图的走廊:[[0, 1], [0, 2], [0, 3], [1, 4], [1, 5], [2, 6], [4, 7], [4, 8]] 共有8条桥。
编号仅标识本次案例中的对象,不能把它当成重要性排名。复算时先保留原输入,再按表格顺序记录中间状态。零值、空列表和未到达各有含义,不能因为显示相似就合并处理。需要分数的地方保存精确值,小数只用于阅读。
结果如何核对
父边不能误当成绕行回边。输出包含每个房间的发现时刻和最早可达时刻,以及全部桥。逐条临时移除走廊再做连通搜索,可以独立核验:只有真正让地图不再连通的边才应列为桥。
桥两侧规模也能帮助判断影响范围,但本例只判断是否断联,并不按客流或重要程度排序。存在绕路不代表绕路短、危险低或允许通过;先把结构连通性与实际游戏代价分开,再分别增加限制。
使用边界
本例没有平行边、自环或单向门。两条不同走廊连接同一对房间时,必须按边身份而不是只按父房间过滤,否则可能误判;有向地图则是另一个可达性问题,不能照搬无向桥的条件。
练习可以先保持其他条件不变,只调整一项输入,观察哪个中间步骤首先产生差异。如果结果不同,先确认单位、端点和同值处理是否一致,再查具体运算。最终答案应与输入和过程一起保存,才方便判断这份结论适用于什么情境。
