并查集主要是两个过程,一个是并,一个是查

原理是用一个数组p[i]保存每个i的根节点,如果根节点一样则在同一个集合里,所以只有根节点p[i]=i;

查:

int find(int x){return p[x]==x?x:p[x]=find(p[x]);}

并:

void Union(int x,int y)

{

  int xx = find(x);int yy=find(y);

  if(xx!=yy)//不在一个集合里

    p[xx]=yy;

}

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std; #define sf scanf
#define pf printf
#define debug printf("!\n")
#define blank printf("\n")
#define mem(a,b) memset(a,b,sizeof(a)) const int MaxN = ;
const int INF = <<; int p[MaxN],a[MaxN]; int m,n; int find(int x){return p[x]==x?x:p[x]=find(p[x]);} void Union(int x,int y)
{
int rx = find(x);
int ry = find(y);
p[rx] = ry;
} int main()
{
int i,j,k;
while(~scanf("%d%d",&n,&m),n+m)
{
i = ;
mem(p,);
mem(a,);
for(j=;j<n;j++)
p[j] = j;
while(m--)
{
sf("%d",&k);
for(i=;i<k;i++)
{
sf("%d",&a[i]);
}
for(i=;i<k;i++)
{
Union(a[i-],a[i]);
}
}
int cnt = ;
for(i = ;i<n;i++)
{
if(find(i)==find())
cnt++;
}
pf("%d\n",cnt);
} return ;
}

最新文章

  1. MVC5 网站开发之八 栏目功能 添加、修改和删除
  2. 教你一招:解决win10/win8.1系统在安装、卸载软件时出现2502、2503错误代码的问题
  3. ClickOnce部署
  4. hrbust1279
  5. 用手机地图GPS导航费流量吗?
  6. 在线运行Javascript,Jquery,HTML,CSS代码
  7. android 删除文件以及递归删除文件夹
  8. C标准库简单解读
  9. View学习(三)- View的布局(layout)过程
  10. EXTENDED LIGHTS OUT poj1222 高斯消元法
  11. MySql中 where IN 字符串
  12. Java开源生鲜电商平台-通知模块设计与架构(源码可下载)
  13. linux下SS 网络命令详解
  14. lunx中部分命令总结
  15. [国家集训队]Crash的数字表格
  16. 【面试 redis】【第十二篇】redis的相关面试问题
  17. linux 执行远程linux上的shell脚本或者命令以及scp 上传文件到ftp--免密码登陆
  18. 【Devops】【docker】【CI/CD】Jenkins自动安装JDK需要提供Oracle的账号密码,否则报错:Unable ro auto-install JDK until the license is accepted
  19. linux C 调用shell程序执行
  20. Linux IO多路复用之epoll网络编程及源码(转)

热门文章

  1. 如何在CentOS 7安装Node.js
  2. [网络] DHCP 之 Mac 绑定
  3. CentOS6.5下openssh服务
  4. tcping测试端口是否畅通
  5. Xcode括号自动补全以及二次编译后不显示输入
  6. HDU-1160-FatMouse&#39;s Speed(线性DP,LIS)
  7. Windows Server2008如何打开添加IIS服务器
  8. vue 在 html 中自定义 tag
  9. 【算法笔记】B1053 住房空置率
  10. UVA_11020 Efficient Solutions 【平衡二叉搜索树set用法】