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