前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >poj----Ubiquitous Religions

poj----Ubiquitous Religions

作者头像
Gxjun
发布2018-03-21 13:06:57
7100
发布2018-03-21 13:06:57
举报
文章被收录于专栏:ml

Ubiquitous Religions

Time Limit: 5000MS

Memory Limit: 65536K

Total Submissions: 20689

Accepted: 10167

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

代码语言:javascript
复制
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

代码语言:javascript
复制
Case 1: 1
Case 2: 7

Hint

Huge input, scanf is recommended.

Source

Alberta Collegiate Programming Contest 2003.10.18

代码:

代码语言:javascript
复制
 1 #include<iostream>
 2 #include<cstdio>
 3 #define maxn 50002
 4 using namespace std;
 5 int Father[maxn],rank[maxn],count;
 6 void makeset(int n)
 7 {
 8     for(int i=1;i<=n;i++)
 9     {
10         Father[i]=i;
11         rank[i]=1;
12     }
13 }
14 
15 int findset(int x)
16 {
17     if(x!=Father[x])
18     {
19         Father[x]=findset(Father[x]);
20     }
21     return Father[x];
22 }
23 
24 void unionset(int fx,int fy)
25 {
26     fx=findset(fx);
27     fy=findset(fy);
28     if(fx==fy)
29         return;
30     if(rank[fx]>rank[fy])
31     {
32         Father[fy]=fx;
33         rank[fx]+=rank[fy];
34         count--;
35     }
36     else
37     {
38         Father[fx]=fy;
39         rank[fy]+=rank[fx];
40         count--;
41     }
42 }
43 
44 int main()
45 {
46     int n,m,st,en,num=1;
47     while(scanf("%d%d",&n,&m),n+m)
48     {
49         makeset(n);
50         count=n;
51         while(m--)
52         {
53             scanf("%d%d",&st,&en);
54             unionset(st,en);
55         }
56       printf("Case %d: %d\n",num++,count);
57     }
58     //system("Pause");
59     return 0;
60 }

http://poj.org/problem?id=2524

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2013-08-17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档