设为首页 加入收藏

TOP

poj-2524-Ubiquitous Religions
2015-07-20 17:45:55 来源: 作者: 【 】 浏览:3
Tags:poj-2524-Ubiquitous Religions
题目大意:一个学校有n人,其中有m对人是具有相同的宗教信仰,
问这个学校里信仰的宗教数最多有多少个。

解题思路:基础的并查集。具有相同信仰的人归为一个集合,

则最后的集合数量即为结果。求集合数量:判断有多少个根节点,用到根节点的特征(其父节点为自己)

代码如下:

#include
  
   
#include
   
     #include
    
      using namespace std; int n,m; int f[52014]; void init() { for(int i=1; i<=n; i++) f[i]=i; } int find(int x) { return f[x]==x?x:find(f[x]); } void unity(int a,int b) { if(find(a)!=find(b)) f[find(a)]=find(b); } int main() { int ji=1; while(cin>>n>>m) { if(n+m==0)break; init(); while(m--) { int a,b; cin>>a>>b; unity(a,b); } int ans=0; for(int i=1; i<=n; i++) if(f[i]==i) ans++; cout<<"Case "<
     
      

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇uva 1556 - Disk Tree(字典树) 下一篇HDOJ 4848 Wow! Such Conquering!

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·如何利用Python做数 (2025-12-24 23:48:36)
·如何使用python进行 (2025-12-24 23:48:34)
·python 爬虫入门该怎 (2025-12-24 23:48:31)
·Java 实现多个大文件 (2025-12-24 23:22:00)
·Java多线程编程在工 (2025-12-24 23:21:56)