题目描述:
世界上宗教何其多。假设你对自己学校的学生总共有多少种宗教信仰很感兴趣。学校有n个学生,但是你不能直接问学生的信仰,不然他会感到很不舒服的。有另外一个方法是问m对同学,是否信仰同一宗教。根据这些数据,相信聪明的你是能够计算学校最多有多少种宗教信仰的。(好,不罗嗦那么多了)
解题思路---->显然并查集了。并查集的详细解释在可以点击 并查集(不相交集合)进行学习。思路可以很清晰的,一开始假设大家都各自信仰一个宗教,那么总的数目ans就是学生数目,每当发现有一对学生信仰同一个宗教,那么ans--;
#include <stdio.h>
#include <iostream>
using namespace std;
const int MAXN = 50005; /*结点数目上线*/
int pa[MAXN]; /*p[x]表示x的父节点*/
int rank[MAXN]; /*rank[x]是x的高度的一个上界*/
int n, ans;
void make_set(int x)
{/*创建一个单元集*/
pa[x] = x;
rank[x] = 0;
}
int find_set(int x)
{/*带路径压缩的查找*/
if(x != pa[x])
pa[x] = find_set(pa[x]);
return pa[x];
}
/*按秩合并x,y所在的集合*/
void union_set(int x, int y)
{
x = find_set(x);
y = find_set(y);
if(x == y)return ;
ans--; //统计
if(rank[x] > rank[y])/*让rank比较高的作为父结点*/
{
pa[y] = x;
}
else
{
pa[x] = y;
if(rank[x] == rank[y])
rank[y]++;
}
}
//answer to 2524
int main()
{
int m, i, j = 1, x, y;
while(scanf("%d%d", &n, &m))
{
if(n == m && m == 0) break;
for(i = 1; i <= n; i++)
make_set(i);
ans = n;
for(i = 0; i < m; i++)
{
scanf("%d%d", &x, &y);
union_set(x, y);
}
printf("Case %d: %d\n", j, ans);
j++;
}
return 0;
}
分享到:
相关推荐
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
并查集是一种用于处理一些不交集的合并及查询问题的数据结构,它支持两种基本操作:合并两个集合(`union`)和查找一个元素所在的集合(`find`)。并查集通常用于解决连通性问题,如图中的顶点是否相连、网络中的...
这题是道神题,神就神在,它既能让你搞懂网络流及其优化,还给了你很大的优化空间。
并查集(Union-Find Sets)是数据结构中一种用于管理元素集合的高效算法,它主要处理两个操作:连接(union)与查找(find)。在并查集中,元素被分到不同的集合中,每个集合代表一个独立的组件。连接操作将两个元素...
1. poj2524.cpp:这是一个POJ(Problem Setter's Online Judge)的编程题目,通常涉及到特定的算法问题,可能需要利用并查集解决连通性或路径查找问题。 2. hdoj1233最小生成树,克鲁斯卡尔.cpp:最小生成树是图论...
学习这些数据结构和算法,并通过实践poj题目来加深理解,是提高ACM竞赛能力的关键步骤。通过初级到高级的题目练习,参赛者能够逐步提升解决问题的能力,应对复杂的编程挑战。在实战中,理解和熟练运用这些知识点,将...
北京大学数据结构与算法课程作业代码,供广大学习c++的同学参考与学习
POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析
北京大学数据结构与算法课程作业代码,供广大学习c++的同学参考与学习
并查集是一种在图论和数据结构中广泛使用的算法,主要用来处理一些不相交集合的合并与查询问题。在给定的标题“1089_bingchaji.rar_1089_bingchaji.rar _并查集”和描述“POJ1089 并查集可以解决 并查集加路径压缩”...
这份代码用C++实现了经典算法并查集,来源于poj题目1182
一种常见的方法是使用深度优先搜索(DFS)或广度优先搜索(BFS)来构建线段之间的连接,并通过并查集(Disjoint Set)数据结构来判断是否存在不相交的集合。 1. **数据结构**:首先,我们需要用数组或者链表存储...
并查集,作为数据结构的一种,主要用于处理一系列的合并及查询问题,特别是在处理大量节点间的连通性问题上表现出色。下面将详细解析并查集的原理、应用场景、以及优化技巧,结合具体代码实例,帮助读者更深入地理解...
并查集基础 acm 算法 poj oi 并查集基础.ppt
数据结构是指解决问题的数据结构,包括串、排序、简单并查集、哈希表和二分查找等高效查找法、哈夫曼树、堆、trie 树等。 * 串:串是指解决问题的基本数据结构,如 poj1035、poj3080、poj1936。 * 排序:排序是指...
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
poj1035、poj3080等训练了串的操作,poj2388、poj2299等则涉及排序问题,poj2524、poj1611等是并查集的实例,poj3349、poj3274等展示了哈希表和二分查找,poj3253是哈夫曼树的题目,poj2442和poj1442则关于堆。...
北京大学在线判题系统POJ(Problem Online Judge)是许多编程爱好者和学习者锻炼算法技能的平台,特别是对于初学者,它提供了很多基础题目来帮助理解并应用数据结构。本资源包含的是北大POJ初级题目的解题报告以及...
在ACM竞赛中,Poj平台上的数据结构题目常常考验选手对算法的深入理解和高效实现。本篇解题报告主要探讨了Pku ACM 3253 Fence Repair问题,这是一道涉及哈夫曼编码(Huffman Coding)的题目。哈夫曼编码是一种用于...