首页 > 代码库 > poj 2524:Ubiquitous Religions（并查集，入门题）

poj 2524:Ubiquitous Religions（并查集，入门题）

2024-07-14 19:14:55   221人阅读

Ubiquitous Religions
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 23997 Accepted: 11807

Description

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 91 21 31 41 51 61 71 81 91 1010 42 34 54 85 80 0

Sample Output

Case 1: 1Case 2: 7

Hint

Huge input, scanf is recommended.

Source

Alberta Collegiate Programming Contest 2003.10.18
 
　　并查集，入门题。
　　题意：
　　一个校园内的所有学生都有宗教信仰，现在要做一个调查，你不能直接问每一个学生，但是可以通过询问他的朋友是否和他的宗教信仰一样，最后需要统计出这个校园内有多少不同的宗教信仰。
　　输入有多组测试数据，每组开头是两个数，n和m，分别表示学校有n名学生和m组询问。后面是m行询问。最后当n和m都为0的时候停止。
　　思路：
　　很明显的并查集问题。将一样的宗教信仰的集合合并，最后写一个for循环统计还有多少不同的信仰即可。
　　注意：
　　每一个人都有宗教信仰，也就是说某一个编号没有在m组询问中出现，不要忽略它，他也是一个信仰。
　　代码：
 1 #include <iostream> 2 #include <stdio.h> 3 using namespace std; 4  5 #define MAXN 50010 6  7 int par[MAXN];    //par[x]表示x的父节点 8 int n; 9 10 void Init()    //初始化11 {12     int i;13     for(i=1;i<=n;i++)14         par[i] = i;15 }16 17 int Find(int x)    //查询x的根节点并路径压缩18 {19     if(par[x]!=x)20         par[x] = Find(par[x]);21     return par[x];22 }23 24 void Union(int x,int y)    //合并x和y所在集合25 {26     par[Find(x)] = Find(y);27 }28 29 int main()30 {31     int m,x,y,i,Case=1;32     while(scanf("%d%d",&n,&m)!=EOF){33         if(n==0 && m==0)34             break;35         //初始化36         Init();    37         //m次询问38         while(m--){39             scanf("%d%d",&x,&y);40             Union(x,y);41         }42         int ans = n;43         for(i=1;i<=n;i++)    //统计44             if(par[i]!=i)45                 --ans;46         printf("Case %d: %d\n",Case++,ans);47     }48     return 0;49 }

 

Freecode : www.cnblogs.com/yym2013


联系
我们