Ubiquitous Religions（并查集）POJ - 2524

There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.

You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.

Input The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.
Output For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.
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
题意：当今世界有太多不同的宗教，很难把它们都记录下来。你想知道你大学里有多少不同宗教的学生信仰宗教。
你知道你们学校有n个学生（0
避免这些问题的一种方法是询问m（0<=m<=n（n-1）/2）对学生，并询问他们是否信仰同一宗教（例如，他们可能知道他们是否都参加了同一个教堂）。
从这些数据中，你可能不知道每个人信仰什么，但你可以了解到有多少不同的宗教可以在校园里代表。你可以假设每个学生最多只信奉一种宗教。



//看了一位大佬的博客，秒懂并查集，初学可以去看看，写的太好了
//附地址：https://blog.csdn.net/niushuai666/article/details/6662911
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include<set>
#include 
#include
#include    
#include
#include
#include
using namespace std;
#define inf 1<<30
#define eps 1e-7
#define LD long double
#define LL long long
#define maxn 100000005
int pre[50009] = {};
int rootsearch(int root)//寻找这个数的领导
{
    int son;
    son = root;
    while (root != pre[root])//这个数不是领导，继续往下找
    {
        root = pre[root];
    }
    while (son != root)//路径压缩，把找到的下级数全部指向最高领导
    {
        int temp = pre[son];
        pre[son] = root;
        son = temp;
    }
    return root;//返回最高领导
}
int main()
{
    int n, m, total;
    int Case = 1;
    while (~scanf("%d%d", &n, &m))
    {
        if (n == 0 && m == 0)break;
        memset(pre, 0, sizeof(pre));
        total = n;//n个集合
        for (int i = 1; i <= n; i++)//一开始，自己是自己的领导
        {
            pre[i] = i;
        }
        while (m--)
        {
            int x, y;
            int root1, root2;
            scanf("%d%d", &x, &y);
            root1 = rootsearch(x);
            root2 = rootsearch(y);
            if (root1 != root2)//两个人的最高领导不同
            {
                pre[root1] = root2;//把第一个集合的最高领导改为第二个集合的最高领导
                total--;//集合数减一
            }
        }
        printf("Case %d: %d\n",Case++, total);
    }
    return 0;
}












						  
					  

						
							


						

							
							
			ACM							
						



						

						
						


						

						
					

					

					
					

						
相关

						

				
						
			

																
								

										
acm讲解

									
									

								 

        

								

							
							

																
								

										
「acmhdu - 6314」Matrix

									
									

								 

        

								

							
							

																
								

										
第十三届河南省ACM-ICPC游记

									
									

								 

        

								

							
							

																
								

										
ACM模板

									
									

								 

        

								

							
							

																
								

										
Hyperf 接入阿里云ACM应用配置管理中心

									
									

								 

        

								

							
							

																
								

										
[ACM] BFS & 双端BFS & A* & 双边BFS

									
									

								 

        

								

							
							

																
								

										
计算几何 / Geometry（ACM-Template 2.0）

									
									

								 

        

								

							
							

																
								

										
ACM入门方式

									
									

								 

        

								

							
							

																
								

										
Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

									
									

								 

        

								

							
							

																
								

										
如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文?

									
									

								 

        

								

							
							

																
								

										
ACM- java在acm中的快速读入，多组读入，快速输出模板

									
									

								 

        

								

							
							

																
								

										
ACM - 动态规划 - P1282 多米诺骨牌

									
									

								 

        

								

							
							
            
            
            
                                    
           
  			
						

					

					
				


				

														
					
					

					
									

					
									   
标签