地图里的某个房间可能是两片区域之间唯一的连接。找出这种关键房间,可以帮助关卡设计检查封路后是否把必经目标彻底隔开。
使用七个房间组成无向图。先计算原图连通区域数,再分别移除一个房间和与它相连的通道,检查剩余房间的区域数;如果区域数比原图更多,就把该房间标为割点。
本例输入与约定
七个房间编号零至六,通道为[[1, 4], [2, 3], [2, 6], [4, 5]]。原连通分组:[[0], [1, 4, 5], [2, 3, 6]]。
完整计算记录
移除房间 | 剩余分组 | 是否割点 0 | [[1, 4, 5], [2, 3, 6]] | False 1 | [[0], [2, 3, 6], [4, 5]] | False 2 | [[0], [1, 4, 5], [3], [6]] | True 3 | [[0], [1, 4, 5], [2, 6]] | False 4 | [[0], [1], [2, 3, 6], [5]] | True 5 | [[0], [1, 4], [2, 3, 6]] | False 6 | [[0], [1, 4, 5], [2, 3]] | False
表中编号仅用于识别本例的元素。读取一个结果时,应先核对它对应的输入、处理顺序和边界约定;布尔值表示条件是否成立,空集合表示没有符合要求的对象,不应把这些字段混成同一种数值。
复核方法与适用范围
移除房间不等于保留它作为一个孤立点,计数时必须把它完全排除。原图不一定连通,因此比较的是区域数量的增加,而不是简单要求移除后只剩一个区域。
这个结论只讨论房间和通道的连接关系,不计算通行时间,也不包含钥匙或临时传送。如果地图规则会增加新的连接,需要对改变后的图重新检查,不能沿用旧结果。
练习时可以先独立计算最前面的一步,再检查最后的整体不变量。若结论不同,应保留各步记录,定位第一处差异;只调整最终数字会掩盖规则理解上的问题。改变输入后也要重新演算,而不是照抄这一例的输出。
