f260: 愛八卦的同學
Tags : disjoint set
Accepted rate : 22人/31人 ( 71% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-13 23:55

Content

在班上,總是會有那麼一兩個同學特別愛說別人閒話。有一天,愛八卦的同學想要知道班上的小團體到底有幾個,他知道班上誰跟誰是朋友,但是因為愛八卦的同學很懶,所以他委託你寫一個程式幫他把小團體的數目計算出來。

Input

多筆測資

每筆測資第一行會有二個正整數 n , k  (int)

n代表班上的人數(編號為0~n-1),k是接下來有幾筆關係

再來有k行,每行有二個整數 a , b 代表編號 a 跟 b 的人是朋友

 

Output

輸出總共有幾個小團體

小團體的定義是你的朋友或者是朋友的朋友跟你屬於同一個小團體

Sample Input #1
5 6
1 0
0 1
1 2
2 3
2 4
4 1
5 4
1 0
0 1
2 3
2 4
Sample Output #1
1
2
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (90%): 0.5s , <10M
Hint :

測資有誤請告知

範例測資第一筆的小團體為 { 0 , 1 , 2 , 3 , 4 }

              第二筆的小團體為 { 0 , 1 } , { 2 , 3 , 4 }

Tags:
disjoint set
出處:
[管理者:
s1082942@g.n... (sellie)
]


ID User Problem Subject Hit Post Date
22605
fire5386 (檸檬紅茶)
f260
C解題方法
62 2020-09-19 12:40