【48.47%】【POJ 2524】Ubiquitous Religions
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 32364 Accepted: 15685
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 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
Hint
Huge input, scanf is recommended.
Source
Alberta Collegiate Programming Contest 2003.10.18
【题解】
最基础的并查集了。
合并之后看看总的“大集合”有多少个即可。
特殊的。只有自己本身的也算成一个宗教。
这样可以满足宗教总数最多。
即同一个宗教的归为一类宗教。其他不同的人的宗教全都不一样。
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 59000;
int n, m;
int f[MAXN];
void input(int &r)
{
char t;
t = getchar();
while (!isdigit(t)) t = getchar();
int x = 0;
while (isdigit(t))
{
x = x * 10 + t - '0';
t = getchar();
}
r = x;
}
int findfather(int x)
{
if (f[x] == x)
return x;
f[x] = findfather(f[x]);
return f[x];
}
int main()
{
//freopen("F:\\rush.txt", "r", stdin);
int ii = 0;
input(n); input(m);
while ((n + m) != 0)
{
ii++;
for (int i = 1; i <= n; i++)
f[i] = i;
int num = n;
for (int i = 1; i <= m; i++)
{
int x, y;
input(x); input(y);
int a = findfather(x), b = findfather(y);
if (a != b)
{
f[a] = b;
num--;
}
}
printf("Case %d: %d\n",ii, num);
input(n); input(m);
}
return 0;
}
最新文章
- 【Win 10应用开发】把文件嵌入到XML文档
- Hypernetes简介
- ios 返回指定导航控制器
- 后台运行程序screen or nohup
- mssql禁用启用主键约束
- Sublime Text3 C++及Java开发环境配置
- javascript设计模式学习之九——命令模式
- HDUOJ--------A simple stone game(尼姆博弈扩展)(2008北京现场赛A题)
- 了解Git
- 使用TensorFlow的卷积神经网络识别自己的单个手写数字,填坑总结
- HEX文件合并方法
- Simple 杂题练手记
- SQLSERVER事务日志已满 the transaction log for database &#39;xx&#39; is full
- 数位dp 模板
- css3 伸缩百分比的调整
- 004-restful应用构建、分布式会话、测试工具简介
- mysql常用函数总结
- jquery插件的几种写法
- Flask中路由系统、Flask的参数及app的配置
- Java VisualVM 插件地址