poj1611 并查集
2024-08-25 14:28:13
题目链接:http://poj.org/problem?id=1611
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector> #define maxn 30050
#define INF 0x3f3f3f
using namespace std;
int pa[maxn]; int find(int x){
return x == pa[x] ? x : pa[x] = find(pa[x]);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)){
if(!n && !m) break;
for(int i=;i<n;i++) pa[i] = i; for(int i=;i<=m;i++){
int k;
scanf("%d",&k);
if(!k) continue;
int a,b;
scanf("%d",&a);
k--;
while(k--){
scanf("%d",&b);
int ta = find(a);
int tb = find(b);
if(ta != tb){
if(ta < tb) pa[tb] = ta;
else pa[ta] = tb;
}
}
}
int ans = ;
for(int i=;i<n;i++){
if(find(i) == ) ans++;
}
printf("%d\n",ans);
}
}
最新文章
- python 安装
- 借助node实战JSONP跨域
- iOS学习之iOS沙盒(sandbox)机制和文件操作之NSFileManager(三)
- UNIX 逐字符输入
- Android(Xamarin)之旅(三)
- JQuery中的push和join
- PNG文件结构分析 ---Png解析
- .net-C#代码判断
- [Angular 2] Inject Service with ";Providers";
- java新手笔记16 面积
- xargs mv命令使用方法:ls *.mp3 |xargs -i mv {} /tmp
- cocos2dx3.1-lua移植android流程
- CF #244 D. Match &; Catch 后缀数组
- angularJS 与angujs-sku实现购物车组合查询
- LVDS、CVBS
- Linux安装Python3后,如何使用pip命令
- Spring容器技术内幕之BeanWrapper类介绍
- 18.0-uC/OS-III挂起内核对象
- vue-router-2-动态路由配置
- 爱今天 APP 闪退怎么办?
热门文章
- IOS DLNA开发(CyberLink和PlatinumKit)
- iOS 数据持久性存储-属性列表
- directsound 应用实例
- Java学习----this和super(在继承中)
- mysql数据类型——浮点和定点型
- yii 验证用户名是否存在 	 				array(";name";,";unique";,&#39;message&#39;=>;&#39;用户名已经存在&#39;),
- [r]Ubuntu Linux系统下apt-get命令详解
- centos 下vmware 下添加硬盘到root
- GNU INET SOCKET
- 优秀的开发者 vs. 差的开发者