#41652: C++詳解-並查集


toseanlin@gmail.com (Dr. SeanXD)

School : 康橋雙語學校
ID : 158065
IP address : [24.147.249.5]
Last Login :
2024-11-30 22:22:32
a445. 新手訓練系列- 我的朋友很少 -- 新手訓練系列 ~ 4 | From: [24.147.249.5] | Post Date : 2024-08-14 22:33

宣告一個陣列代表每一個人的最底層朋友是誰,每一個人預設值為 0。如果收到人的時候這個人的陣列值為 0,代表還沒有紀錄,所以將陣列值設為自己。

宣告一個函式 findEnd 用來尋找最底層的朋友,有一個參數 N,如果 N 的陣列值為 0 或是自己就 return N,否則就 return findEnd(陣列值[N])。

收到資料的時候將 陣列值[findEnd(B)] 設為 findEnd(A)。最後只需要確認 陣列值[P] 是否等於 陣列值[Q],如果相同就代表這兩人是朋友。

 

範例程式碼

 
ZeroJudge Forum