前往
大廳
主題

ZeroJudge - f677: FJCU_109_Winter_Day3_Lab1 並查集練習 解題心得

Not In My Back Yard | 2021-03-06 00:00:13 | 巴幣 0 | 人氣 272

題目連結:


題目大意:
輸入第一列給定兩正整數 N 、 M (範圍未知,但經測不超過 100),代表有 N 個人(編號 0 ~ N - 1)以及 M 筆接觸史。接下來有 M 列輸入,每列給定兩整數 a 、 b (0 ≦ a 、 b < N),代表編號 a 與編號 b 有過接觸。

試問有多少人與編號 0 這個人直接或是間接地(接觸過直接或間接接觸的人)接觸?



範例輸入:
5 3
1 0
0 3
2 4


範例輸出:
3


解題思維:
如題目標題所述,這題可以使用併查集(做法以及定義直接參見維基頁面即可)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作