斷一條路:哪些地點會失聯
在小型網絡中識別唯一連接邊並判斷斷開影響。
影片暫時無法載入。請檢查網絡後重試,或直接下載影片。
下載影片
展開影片文字稿
- A、B、C三村两两有路,构成三角形;D只通过道路C到D连接网络。
- 先看D的连接表,它只有C到D这一条边,没有第二条替代路线。
- 封闭C到D后,D没有任何出口,所以D与其余村失去联系。
- A、B、C之间的三条道路仍保留,任意两村仍可直接到达。
- 逐点做可达检查,只有D失败;这条唯一连接边控制了D的连通。
- 挑战换成E、F、G成三角形,G再连H。请划掉G到H并检查谁失联,小宝贝到你了。
邏輯思維
刪邊後從每點做可達遍歷。
看一個例子
村A-B-C構成三角形,C還通過唯一道路連D。封閉C-D後,誰與其餘村失聯?
刪C-D後D失聯,ABC互通。刪邊後從每點做可達遍歷。
立即試一題
W只有Z-W一條出口。