POJ1611-The Suspects-并查集
2024-10-14 21:27:46
记录元素个数的并查集。
利用sz数组保存并查集的大小。每次union时,把小的集合并到大的中去,并更新sz数组。
#include <cstdio>
#include <algorithm> using namespace std; int n,m,k; int fa[],sz[]; int Find(int x)
{
while(x != fa[x])
{
fa[x] = fa[fa[x]];
x = fa[x];
}
return x;
} void Union(int p,int q)
{
int fp = Find(p),fq = Find(q);
if(fp == fq) return;
if(sz[fp] < sz[fq])
{
fa[fp] = fq;
sz[fq] += sz[fp];
}
else
{
fa[fq] = fp;
sz[fp] += sz[fq];
}
} int main()
{
while(scanf("%d%d",&n,&m) && (n||m))
{
for(int i=;i<n;i++)
{
fa[i] = i;
sz[i] = ;
}
for(int i=;i<m;i++)
{
scanf("%d",&k);
int root = ,p;
for(int i=;i<k;i++)
{
scanf("%d",&p);
if(!i) root = p;
else Union(p,root);
}
}
printf("%d\n",sz[Find()]);
}
}
最新文章
- zabbix-agent配置文件说明
- Scala入门之函数
- iOS 准确计算某个时间点距现在的时间差的代码 如";几分钟,几小时,几秒之前"; ,
- sublime text2 常用快捷键
- #你好Unity3D#Project脚本执行双击资源操作
- 随笔 planetest
- NYOJ-655 光棍的YY AC 分类: NYOJ 2013-12-29 19:24 224人阅读 评论(0) 收藏
- win7系统中的声音图标不见了怎么办
- HTML常用标签和属性大全
- C#_Queue实例
- poi导出word
- SQL Server 系统时间
- SQL Server数据库附加失败:错误5120和错误950
- Windows下nginx下安装amqp
- Nginx 配置下载附件让浏览器提示用户是否保存
- Android 集成ShareSDK分享QQ或空间成功后,回调却不执行的原因
- Flexbox 布局的最简单表单 (转)
- chrome浏览器访问Google的插件“谷歌访问插件”以及常用插件
- 修改socket文件, MySQL启动报错
- Oracle VM VirtualBox做好虚拟硬盘后,如何进一步修改虚拟硬盘的大小