首页 > 代码库 > poj2524(Ubiquitous Religions)
poj2524(Ubiquitous Religions)
题目大意:
一个学校里有N个学生,但每个学生对宗教的信仰不同。有M对同学,每一对的同学对宗教的信仰是相同的,让你求N个同学里最多有多少同学信仰着不同的宗教。
解题思路:
简单并查集。先建树,信仰同一宗教的同学在一个树上,然后查找有几棵树就可以了,查找多少棵树的方法就是统计祖先是是本身的个数即可。
代码:
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 #include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int dx[]= {0,-1,0,1}; 25 const int dy[]= {1,0,-1,0}; 26 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 27 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 28 /***************************************/ 29 void openfile() 30 { 31 freopen("data.in","rb",stdin); 32 freopen("data.out","wb",stdout); 33 } 34 /**********************华丽丽的分割线,以上为模板部分*****************/ 35 #define MAX 50001 36 int pre[MAX],rank[MAX]; 37 void makeset(int i) 38 { 39 pre[i]=i; 40 rank[i]=0; 41 } 42 int find(int x) 43 { 44 if (x!=pre[x]) 45 { 46 pre[x]=find(pre[x]); 47 return pre[x]; 48 } 49 return x; 50 } 51 void unionone(int a,int b) 52 { 53 int t1=find(a); 54 int t2=find(b); 55 if (rank[t1]<=rank[t2]) 56 { 57 pre[t1]=t2; 58 rank[t2]+=rank[t1]; //rank[k]包含子集个数。 59 } 60 else 61 { 62 pre[t2]=t1; 63 rank[t1]+=rank[t2]; 64 } 65 } 66 int main() 67 { 68 int n,m; 69 int cas=0; 70 while(scanf("%d%d",&n,&m)&&(n+m)) 71 { 72 int i,j; 73 int a,b; 74 for(i=1; i<=n; i++) 75 makeset(i); 76 for(i=0; i<m; i++) 77 { 78 scanf("%d%d",&a,&b); 79 unionone(a,b); 80 } 81 int cnt=0; 82 for(j=1; j<=n; j++) 83 if (j==find(j)) 84 cnt++; 85 printf("Case %d: ",++cas); 86 printf("%d\n",cnt); 87 } 88 return 0; 89 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。