| Time Limit: 5000MS | Memory Limit: 65536K | |
| Total Submissions: 22334 | Accepted: 10996 |
Description
Input
Output
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
本题要计算一个小组中最多有多少种不同的信仰，只需用小组的人数减去已有小组内人数的总数，再加上小组的数目，就得到了结果。
如果两个节点不在一个小组，则要合并他们，用MaxNum-2+1，MaxNum减去小组内两个人，还要加1的小组数目，所以只需要在合并两个不同节点时用MaxNum--即可。
代码：
1 #include <iostream> 2 using namespace std; 3 4 int father[50001], num[50001]; 5 int count = 0; 6 int MaxNum; 7 8 void MakeSet(int x) 9 { 10 father[x] = x; 11 num[x] = 1; 12 } 13 14 int FindSet(int x) 15 { 16 if(x != father[x]) 17 father[x] = FindSet(father[x]); 18 return father[x]; 19 } 20 21 void Union(int x, int y) 22 { 23 int GrandX = FindSet(x); 24 int GrandY = FindSet(y); 25 26 if(GrandX == GrandY) 27 return; 28 if(num[GrandX] < num[GrandY]) 29 { 30 father[GrandX] = GrandY; 31 num[GrandY] += num[GrandX]; 32 } 33 else 34 { 35 father[GrandY] = GrandX; 36 num[GrandX] += num[GrandY]; 37 } 38 MaxNum--; 39 } 40 41 int main() 42 { 43 int n, m; 44 int Case = 0; 45 46 while((cin >> n, cin >> m) && !(m==0 && n==0)) 47 { 48 MaxNum = n; 49 for(int i = 0; i < n; i++) 50 MakeSet(i); 51 for(int i = 0; i < m; i++) 52 { 53 int x, y; 54 cin >> x >> y; 55 Union(x, y); 56 } 57 cout << "Case " << ++Case << ": " << MaxNum << endl; 58 } 59 }
原文：http://www.cnblogs.com/horizonice/p/3658246.html