POJ 2524 并查集的水题 Ubiquitous Religions

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

单纯的并查集的题目所以比较简单

需要注意的是由于读入的数据量比较大所以读入用scanf比较好

#include<cstdio>
#include<set>
#define size_num 51000
using namespace std;
set<int> sett;//用集合可以方便的知道不同的元素的个数
int p[size_num];
int findp(int x){return p[x]==x?x:p[x]=findp(p[x]);}
int deal()
{int a,b,n,m;static int cas=0;scanf("%d%d",&n,&m);if(!n&&!m) return 0;for(int i=1;i<=n;i++) p[i]=i;//初始化并查集for(int i=0;i<m;i++){scanf("%d%d",&a,&b);int x=findp(a),y=findp(b);p[x]=y;}for(int i=1;i<=n;i++)sett.insert(findp(i));printf("Case %d: %d\n",++cas,sett.size());sett.clear();return 1;
}
int main()
{while(deal());return 0;
}

不用集合实现的版本，也没快多少。。

#include<cstdio>
#define size_num 51000
#include<cstring>
using namespace std;
int p[size_num];
bool flag[size_num];//用来标记是否是根
int findp(int x){return p[x]==x?x:p[x]=findp(p[x]);}
int deal()
{int a,b,n,m,ans=0;static int cas=0;memset(flag,0,sizeof(flag));scanf("%d%d",&n,&m);if(!n&&!m) return 0;for(int i=1;i<=n;i++)p[i]=i;//初始化并查集for(int i=0;i<m;i++){scanf("%d%d",&a,&b);a=findp(a),b=findp(b);p[a]=b;}for(int i=1;i<=n;i++)flag[findp(i)]=1;for(int i=0;i<=n;i++)if(flag[i])ans++;printf("Case %d: %d\n",++cas,ans);return 1;
}
int main()
{while(deal());return 0;
}

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

---