d813: 10583 - Ubiquitous Religions
Tags :
Accepted rate : 193人/227人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-10-20 14:29

Content

這個世界上有許多不同的宗教信仰。你想要知道你就讀的大學中,學生們到底信了多少種不同的宗教。

在你就讀的大學中共有 n 個學生 ( 0 < n <= 50000 )。顯然你不可能對每個人個別詢問他們的信仰,而且某些學生也不方便透露他們所信的宗教。而解決這些問題的一種可能的方法是詢問 m ( 0 <= m <= n(n-1)/2 )對學生他們是否信同一個宗教 (例如他們可能一起去某間教堂,會知道他們彼此信相同的宗教 )。由這些資料,即使你沒辦法知道每個人信哪個教,但是你可以估計出他們最多信了多少種不同的宗教。你可以假設每個學生最多信一個宗教。

Input

輸入中包含了許多的測試資料。每筆測試資料由一列包含兩個整數 n 及 m 作為開頭。接下來的 m 列每列包含了兩個整數 i 和 j,代表學生 i 和學生 j 信同一個宗教。這些學生編號為 1 到 n。

當 n = m = 0 的時候代表輸入結束。

Output
對於每筆測試資料,請先輸出測試資料的編號(由1開始),然後輸出學生們最多信了多少種不同的宗教。
Sample Input
10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0
Sample Output
Case 1: 1
Case 2: 7
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <10M
Hint :

※ 譯 Lucky貓

※  并查集

※ 請用EOF做結尾,測資不易重生...

Tags:
出處:
UVa10583 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」