首页 > 代码库 > POJ 2524 Ubiquitous Religions 【并查集】
POJ 2524 Ubiquitous Religions 【并查集】
解题思路：输入总人数 n,和m组数据；即和杭电畅通工程相类似，对这m组数据做合并操作后，求最后一共有多少块区域。
#include<stdio.h>int pre[50001];int find(int root){ if(root!=pre[root]) pre[root]=find(pre[root]); return pre[root];}void unionroot(int x,int y){ int root1,root2; root1=find(x); root2=find(y); if(x!=y) { pre[root1]=root2; }}int main(){ int n; int i; int x,y; long int m; int tag=1; while(scanf("%d %d",&n,&m)!=EOF&&(n||m)) { int sum=0; for(i=0;i<n;i++) pre[i]=i; while(m--) { scanf("%d %d",&x,&y); unionroot(x,y); } for(i=0;i<n;i++) { if(find(i)==i) sum++; } printf("Case %d: %d\n",tag,sum); tag++; }}
POJ 2524 Ubiquitous Religions 【并查集】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。