poj 并查集 - 2524 Ubiquitous Religions

本文主要是介绍poj 并查集 - 2524 Ubiquitous Religions，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

并查集题目，并的意思就是将两个不同类别的集合合并到一起，类似于两棵树合并；查的意思就是找到这个点所属集合的根节点。基本上并查集题目都是在大体架构上面加一些东西即可。并查集代码模板在这里点击打开链接

每个人都可能有不同的信仰，有n个学生，给出一些line，每个line里的两个人信仰一样，最后判断有n个学生中最多有多少信仰。

我们在原本模板上加入一个记录信仰数的变量num，一开始num=n，在合并两个有相同信仰的学生时，如果两人的根结点不同，则num--； 如果两人的根结点相同，说明这两个人已经被判断过，不用减。

#include<stdio.h>
const int MAXN = 50002; 
int pa[MAXN]; 
int num;void make_set(int size)  
{int i;for(i=1;i<=size;i++){pa[i] = i;}
}  int find_set(int x)  
{ int temp;if(x==pa[x])  return x;  temp = pa[x];pa[x]=find_set(temp);return pa[x];  
}  void union_set(int x,int y)  
{  int xx,yy;xx=find_set(x);yy=find_set(y);if(xx!= yy){num--;}pa[yy]=xx;}  int main()  
{  int  i,j,m,n,size=1;while(scanf("%d %d",&n,&m) && n!=0 && m!= 0){make_set(n);num=n;while(m--){scanf("%d %d",&i,&j);union_set(i,j);}printf("Case %d: %d\n",size++,num);}return 0;  
}  

这篇关于poj 并查集 - 2524 Ubiquitous Religions的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---