1
A
回答
1
島是一個節點的集合,這樣你就可以從一個節點遍歷到另一個節點而不會跨越任何橋。沒有連接到任何其他節點的單個節點是島。
島鏈是由橋樑連接的一系列島嶼。島鏈是無環的;如果你通過一座橋離開一個島,除了同一座橋,你不能回到島上。請注意,這與組成島鏈節點的集合是非循環的並不相同;個別島嶼可能包含循環。
當添加的邊緣圖表,遵循這些原則,讓你的鏈條,島嶼,橋樑的軌道:
如果一個新的邊緣補充說,一個島嶼連接到本身,即邊緣不是一座橋。橋樑總數保持不變。
如果兩個島嶼是不一樣的島鏈的一部分,一個新的邊緣添加連接它們,那麼邊緣變成一座橋,這兩個島鏈合併成一個單一的島鏈。
如果兩個島嶼是島鏈的一部分,並且增加了連接它們的新邊緣,則必須合併一些島嶼以維護非循環屬性。通過連接兩個島嶼的島鏈尋找路徑。對於以這種方式遍歷的所有島嶼,包括兩端的島嶼,將它們全部合併成一個島嶼。你以這種方式穿過的任何橋樑都不再成爲橋樑。
通過這些步驟,您可以在添加邊緣的同時保持圖形中橋接的數量。從未連接的節點開始。每個節點都是一個島鏈,其中包含一個島,其中包含一個節點。當您添加邊緣時,請參閱上面的三條規則以根據需要合併島嶼和島嶼鏈。
島可以表示爲一組節點,島鏈可以表示爲島的無向非循環圖。算法中最昂貴的部分是找到兩個現有島之間的路徑;直覺上,我猜測鏈中的島數會相對於n
保持較小,因此總體複雜度將接近O(m)時間。
相關問題
- 1. 團結GetAxis增量計算
- 2. 計算對象增量
- 3. 計算工資增量
- 4. 計算網站中的頁面數量
- 5. 視網膜屏幕增加計算
- 6. 在java中計算圖(網絡)中節點的數量
- 7. 無法提取增量和增量delta功率譜計算
- 8. 計算增長率和兩個變量
- 9. 如何正確計算時間增量?
- 10. R:計算增量在時間序列
- 11. 使用java計算增量平均值
- 12. R選項隱含增量計算
- 13. 計算圖像中對象的數量
- 14. 計算位圖中「孔」的數量
- 15. 在R中循環創建計算的增量列
- 16. 使用最大內存效率的增量中值計算
- 17. 使用分區計算Pandas中條目之間的增量
- 18. R數據表中的計算時間增量
- 19. 如何計算Oracle 11g中存儲使用量的增加?
- 20. 計算網絡的最大流量
- 21. 計算B類網絡中每個子網的主機數量
- 22. 什麼是增強庫中計算Voronoi圖的邊界框
- 23. Angularjs計數增量
- 24. MySQL中的產量計算
- 25. Netlogo:計算圖形/網絡的直徑
- 26. CSS,增加100%[計算(100%+ __)
- 27. 爲某些網址計算瀏覽量
- 28. 如何計算我的倉庫每天的平均增長量?
- 29. 計算大小遞增的矢量的平均值
- 30. CSS計算與計算的變量
是的,我是。現在似乎很滑稽。你的想法在時間內似乎是可以實現的。我會編寫代碼並返回。謝謝!! – frodo 2012-07-19 16:20:55