內容 ：
這個世界上有許多不同的宗教信仰。你想要知道你就讀的大學中，學生們到底信了多少種不同的宗教。
在你就讀的大學中共有 n 個學生 ( 0 < n <= 50000 )。顯然你不可能對每個人個別詢問他們的信仰，而且某些學生也不方便透露他們所信的宗教。而解決這些問題的一種可能的方法是詢問 m ( 0 <= m <= n(n-1)/2 )對學生他們是否信同一個宗教 (例如他們可能一起去某間教堂，會知道他們彼此信相同的宗教 )。由這些資料，即使你沒辦法知道每個人信哪個教，但是你可以估計出他們最多信了多少種不同的宗教。你可以假設每個學生最多信一個宗教。
輸入說明 ：
輸入中包含了許多的測試資料。每筆測試資料由一列包含兩個整數 n 及 m 作為開頭。接下來的 m 列每列包含了兩個整數 i 和 j，代表學生 i 和學生 j 信同一個宗教。這些學生編號為 1 到 n。
當 n = m = 0 的時候代表輸入結束。
輸出說明 ：
對於每筆測試資料，請先輸出測試資料的編號(由1開始)，然後輸出學生們最多信了多少種不同的宗教。
範例輸入 ：
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
範例輸出 ：
Case 1: 1
Case 2: 7
提示 ：
※ 譯 Lucky貓
※ 并查集
※ 請用EOF做結尾，測資不易重生...
出處 ：
UVA 10583 (管理：morris1028)
Dim SP, Kinds, Ti
回覆刪除Private Sub Form_Load()
Me.Hide
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Ti = 0
Do While Not EOF(1)
Input #1, n, m
List1.Clear
Kinds = 1
If n <> "0" And m <> "0" Then
Ti = Ti + 1
ReDim SP(n)
For i = 0 To n: SP(i) = 0: Next
For i = 1 To m
Line Input #1, X
List1.AddItem X
Next
Call A1
Print #2, "Case " & Ti & ":"; Kinds - 1
End If
Loop
Close
Close
End
End Sub
Sub A1()
Dim KK, P, PP
For i = 0 To List1.ListCount - 1
PP = List1.List(i)
P = Split(PP)
If SP(P(0)) = "0" Then
SP(P(0)) = Kinds: SP(P(1)) = Kinds: Kinds = Kinds + 1
Else
SP(P(1)) = SP(P(0))
End If
Next
For i = 1 To UBound(SP)
Print SP(i) & "-" & i
If SP(i) = "0" Then Kinds = Kinds + 1
Next
End Sub
Dim X()
回覆刪除Dim s
Private Sub Form_Load()
Me.Hide
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
T = 0
Do While Not EOF(1)
T = T + 1
List1.Clear
Input #1, N, M
If N <> 0 Then
ReDim X(N)
For i = 1 To N
X(i) = 0
Next i
s = 1
For i = 1 To M
Input #1, A, B
If X(A) = X(B) And X(A) = 0 Then X(A) = s: X(B) = s: s = s + 1
If X(A) < X(B) Then
If X(A) = 0 Then X(A) = X(B) Else Call Replace_Same(X(A), X(B))
End If
If X(A) > X(B) Then
If X(B) = 0 Then X(B) = X(A) Else Call Replace_Same(X(B), X(A))
End If
Next i
Print #2, C()
End If
Loop
Close #2
Close #1
End
End Sub
Sub Replace_Same(Q, W)
For i = 1 To UBound(X)
If X(i) = W Then X(i) = Q
Next i
End Sub
Function C()
ans = 0
For i = 1 To UBound(X)
If X(i) = 0 Then ans = ans + 1
If X(i) <> 0 Then If re(X(i)) = False Then List1.AddItem X(i)
Next i
ans = ans + List1.ListCount
C = ans
End Function
Function re(Q) As Boolean
P = False
For i = 0 To List1.ListCount - 1
If List1.List(i) = Q Then P = True: Exit For
Next i
re = P
End Function
in-----------
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
2 8
10 6
2 3
4 5
6 7
7 2
2 1
5 6
10 5
2 3
4 5
6 7
7 2
2 1
0 0
out---------------
1
6
4
5
http://zerojudge.tw/ShowProblem?problemid=a216
回覆刪除這題 做做看 :D
arro好，
回覆刪除1程式ok。
2你將檔案資料讀進來，串在一起放在listbox，再從listbox拿出來，用split將它分開，是不是重複動作了，浪費了不必要的時間與動作。
佑好，
1程式ok。
2程式用了連兩層的函數呼叫，然後外頭又共用陣列，很容易想法打結而出錯。