首页 > 代码库 > poj1611 并查集 (路径不压缩)
poj1611 并查集 (路径不压缩)
http://poj.org/problem?id=1611
题目大意：
有一个学校，有N个学生，编号为0-N-1，现在0号学生感染了非典，凡是和0在一个社团的人就会感染，并且这些人如果还参加了别的社团，他所在的社团照样全部感染，求感染的人数。
解题思路：
并查集的变种，实质就是求0所在的强连通图的结点数目。
这道题纠结在数据的输入上，他只是告诉你哪些学生是同一个社团的。这就需要处理一下，我的想法是：如果这个社团有num个孩子，new出一个大小为num的数组，第一个孩子不处理，从第二个孩子起，和上个孩子合并，这样就完成了他们的合并。
AC代码：
#include<iostream>#include<cstdio>using namespace std;int p[30005],b[30005],r[30005],num[30005];int n,m,k;int Find(int x){ if(p[x]!=x) p[x]=Find(p[x]); return p[x];}void Union(int x,int y){ //x=Find(x); //y=Find(y); if(x==y) return; if(r[x]>r[y]) { p[y]=x; num[x]+=num[y]; } else { p[x]=y; if(r[x]==r[y]); r[y]++; num[y]+=num[x]; }}int main(){ while(scanf("%d%d",&n,&m)&&(m+n)) { for(int i=0; i<n; i++) { p[i]=i; r[i]=0; num[i]=1; } while(m--) { scanf("%d",&k); for(int i=1; i<=k; i++) scanf("%d",&b[i]); for(int i=1; i<k; i++) { int x=Find(b[i]); int y=Find(b[i+1]); Union(x,y); } } int p=Find(0); printf("%d\n",num[p]); } return 0;}
poj1611 并查集 (路径不压缩)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。