POJ1611基础带权并查集
基础 查集
2023-09-11 14:14:00 时间
题意:
有一个人生病了,和他一个社团或者间接和他有联系的人都会生病,问一共有多少人生病了。
思路:
比较简单和基础的题,带权并查集中的一种,就是记录更新集合元素个数,这个题目我是开始的时候每个人自己在自己的集合里,元素个数是1,然后在多开出来m个集合,让第i个社团直接映射到i+n个集合,元素个数一开始是0,然后就是简单更新了,还有就是注意下两个人已经属于同一个集合的时候就直接跳过,不用处理。
#include<stdio.h>
#include<string.h>
#define N 30000 + 500 + 10
int mer[N] ,sum[N];
int finds(int x)
{
return x == mer[x] ? x : mer[x] = finds(mer[x]);
}
int main ()
{
int n ,m ,i ,a ,k;
while(~scanf("%d %d" ,&n ,&m) && n + m)
{
for(i = 1 ;i <= n + m ;i ++)
{
if(i <= n) sum[i] = 1;
else sum[i] = 0;
mer[i] = i;
}
for(i = 1 ;i <= m ;i ++)
{
scanf("%d" ,&k);
int y = finds(i+n);
while(k--)
{
scanf("%d" ,&a);
++a;
int x = finds(a);
if(x == y) continue;
mer[x] = y;
sum[y] += sum[x];
}
}
int x = finds(1);
printf("%d\n" ,sum[x]);
}
return 0;
}
有一个人生病了,和他一个社团或者间接和他有联系的人都会生病,问一共有多少人生病了。
思路:
比较简单和基础的题,带权并查集中的一种,就是记录更新集合元素个数,这个题目我是开始的时候每个人自己在自己的集合里,元素个数是1,然后在多开出来m个集合,让第i个社团直接映射到i+n个集合,元素个数一开始是0,然后就是简单更新了,还有就是注意下两个人已经属于同一个集合的时候就直接跳过,不用处理。
#include<stdio.h>
#include<string.h>
#define N 30000 + 500 + 10
int mer[N] ,sum[N];
int finds(int x)
{
return x == mer[x] ? x : mer[x] = finds(mer[x]);
}
int main ()
{
int n ,m ,i ,a ,k;
while(~scanf("%d %d" ,&n ,&m) && n + m)
{
for(i = 1 ;i <= n + m ;i ++)
{
if(i <= n) sum[i] = 1;
else sum[i] = 0;
mer[i] = i;
}
for(i = 1 ;i <= m ;i ++)
{
scanf("%d" ,&k);
int y = finds(i+n);
while(k--)
{
scanf("%d" ,&a);
++a;
int x = finds(a);
if(x == y) continue;
mer[x] = y;
sum[y] += sum[x];
}
}
int x = finds(1);
printf("%d\n" ,sum[x]);
}
return 0;
}
相关文章
- CSS动画基础:常用动画效果的设置
- C# 基础 字符串 集合 文件操作
- 基础大杂烩 -- 目录
- python基础(一)列表与元组
- 音视频开源基础学习 - 编译ffmpeg
- 整理了一周近万字讲解linux基础开发工具vim,gdb,gcc,yum等的使用
- Java基础语法:1.第一个java程序
- PHP学习笔记_04_基础入门
- 《C++ 开发从入门到精通》——2.4 输入输出基础
- SwiftUI 学习方法之 04 我是真正的0基础,现在还没开始写App就已经很害怕了
- Java高频面试题合集——【Java基础、IO流、Java异常、Java集合、Java并发】高频面试题汇总
- goj基础环境的配置
- 【Verilog基础】【计算机体系架构】ITCM和ICACHE对比(面试常问)
- 【SystemVerilog基础】SystemVerilog语法之逻辑等(==)、全等(===)和匹配等(==?)
- Python 基础 之 Ubuntu 上安装 python 和 python-pip