發表新討論
#18692:


lltzpp (lltzpp)

學校 : 國立成功大學
編號 : 47754
來源 : [112.78.95.38]
最後登入時間 ：
2024-10-19 10:23:34
b517. 是否為樹-商競103 -- 103學年度商業類程式設計競賽模擬題 | From: [42.77.0.94] | 發表日期 : 2019-07-28 22:46

開一個並查集，如果這個邊的兩端點已經在同一個並查集裡面那就直接輸出false，反之則把兩端點所在的並查集合併

開並查集的時候順便紀錄這個並查集的大小，最後再隨便戳一個點，並查詢此並查集大小，如果並查集大小與輸入的節點數量相同，那麼這張圖就是一棵樹（此圖都是聯通的

實作一下run time只有2ms

 
ZeroJudge Forum