记录元素个数的并查集。

利用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()]);
}
}

最新文章

  1. zabbix-agent配置文件说明
  2. Scala入门之函数
  3. iOS 准确计算某个时间点距现在的时间差的代码 如&quot;几分钟,几小时,几秒之前&quot; ,
  4. sublime text2 常用快捷键
  5. #你好Unity3D#Project脚本执行双击资源操作
  6. 随笔 planetest
  7. NYOJ-655 光棍的YY AC 分类: NYOJ 2013-12-29 19:24 224人阅读 评论(0) 收藏
  8. win7系统中的声音图标不见了怎么办
  9. HTML常用标签和属性大全
  10. C#_Queue实例
  11. poi导出word
  12. SQL Server 系统时间
  13. SQL Server数据库附加失败:错误5120和错误950
  14. Windows下nginx下安装amqp
  15. Nginx 配置下载附件让浏览器提示用户是否保存
  16. Android 集成ShareSDK分享QQ或空间成功后,回调却不执行的原因
  17. Flexbox 布局的最简单表单 (转)
  18. chrome浏览器访问Google的插件“谷歌访问插件”以及常用插件
  19. 修改socket文件, MySQL启动报错
  20. Oracle VM VirtualBox做好虚拟硬盘后,如何进一步修改虚拟硬盘的大小

热门文章

  1. C++11 并发指南四(&lt;future&gt; 详解一 std::promise 介绍)
  2. php WNMP(Windows+Nginx+Mysql+php)配置笔记
  3. SRP周记_20190418
  4. Caffe源码中math_functions文件分析
  5. mysql大数据量下的分页
  6. NTP服务部署和测试
  7. Nginx反向代理的简单实现
  8. Python练习-8
  9. Week2 关于代码规范的一些认识
  10. ELF分析 实践