在旦旦國有N個城市,在每個城市之間有許多道路可以通往彼此,但也有可能有些城市沒有對外聯通的道路,假設x城市和y城市之間有路可以通往彼此,我們稱x城市和y城市在同一個都會區(若某個城市沒有跟任何其他的城市有連通,則自己為一個都會區),而鵝鵝騎士對旦旦國的風景特別喜歡,想要到旦旦國每個城市都去遊玩一次,但是如果每次要去的城市要橫跨不同都會區的話,會花非常多時間在交通上,因此每次他都只去一個都會區觀光,並且把都會區內的所有城市都去過一遍。現在我們想知道鵝鵝騎士最少要來旦旦國幾次才能把每個城市都探索過一遍?以及分別計算每個都會區有幾個城市以方便鵝鵝騎士規劃他的時間和行程
第一行有一個正整數T代表測資數量。
每筆測資第一行有兩個正整數N,M,分別代表城市數量與道路數量。
接下來有M行每行兩個正整數ai,bi代表ai和bi之間有路相連。
20%測資符合1≤N,M≤1000
40%測資符合1≤N≤1000,1≤M≤105
100%測資符合1≤N,M≤105,1≤ai,bi≤N,1≤T≤5
每筆測資輸出兩行。第一行輸出一個正整數代表有幾個都會區的數量,第二行由小到大輸出每個都會區的城市數量。
1 8 6 1 2 3 4 1 5 5 3 2 4 6 8
3 1 2 5
範測中,{1,2,3,4,5}、{6,8}、{7}分別為三個連通塊。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |