体育新闻

移除哪个房间会让原本相通的区域断开:规则练习第18例

2026-11-09

地图里的某个房间可能是两片区域之间唯一的连接。找出这种关键房间,可以帮助关卡设计检查封路后是否把必经目标彻底隔开。

使用七个房间组成无向图。先计算原图连通区域数,再分别移除一个房间和与它相连的通道,检查剩余房间的区域数;如果区域数比原图更多,就把该房间标为割点。

本例输入与约定

七个房间编号零至六,通道为[[1, 3], [1, 6], [2, 3], [2, 4], [2, 5]]。原连通分组:[[0], [1, 2, 3, 4, 5, 6]]。

完整计算记录

移除房间 | 剩余分组 | 是否割点 0 | [[1, 2, 3, 4, 5, 6]] | False 1 | [[0], [2, 3, 4, 5], [6]] | True 2 | [[0], [1, 3, 6], [4], [5]] | True 3 | [[0], [1, 6], [2, 4, 5]] | True 4 | [[0], [1, 2, 3, 5, 6]] | False 5 | [[0], [1, 2, 3, 4, 6]] | False 6 | [[0], [1, 2, 3, 4, 5]] | False

表中编号仅用于识别本例的元素。读取一个结果时,应先核对它对应的输入、处理顺序和边界约定;布尔值表示条件是否成立,空集合表示没有符合要求的对象,不应把这些字段混成同一种数值。

复核方法与适用范围

移除房间不等于保留它作为一个孤立点,计数时必须把它完全排除。原图不一定连通,因此比较的是区域数量的增加,而不是简单要求移除后只剩一个区域。

这个结论只讨论房间和通道的连接关系,不计算通行时间,也不包含钥匙或临时传送。如果地图规则会增加新的连接,需要对改变后的图重新检查,不能沿用旧结果。

练习时可以先独立计算最前面的一步,再检查最后的整体不变量。若结论不同,应保留各步记录,定位第一处差异;只调整最终数字会掩盖规则理解上的问题。改变输入后也要重新演算,而不是照抄这一例的输出。