当前位置: 首页 > news >正文

图论-并查集

并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题.一些常见的用途有求连通子图,求最小生成树Kruskal算法和最近公共祖先(LCA)等.

并查集的基本操作主要有:

.1.初始化

2.查询find

3.合并union

 

一般我们都会采用路径压缩 这样效率更加高  

 

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define MAXN 20001
int fa[MAXN];
void init(int n) {for (int i = 1; i <= n; i++) {fa[i] = i;}//初始化
}
int find(int x) {if (x == fa[x]) {return x;}else {fa[x] = find(fa[x]);//路径压缩 也就是一直找到祖先return fa[x];}
}
void unionn(int i, int j) {int i_fa = find(i);//找到i的祖先int j_fa = find(j);//找到j的祖先fa[i_fa] = j_fa;//i的祖先指向j的祖先 反过来也可以
}
int main() {int n, m, x, y, q;scanf("%d", &n);init(n);scanf("%d", &m);for (int i = 1; i <= m; i++) {scanf("%d%d", &x, &y);unionn(x, y);}scanf("%d", &q);for (int i = 1; i <= q; i++) {scanf("%d%d", &x, &y);if (find(x) == find(y)) {printf("Yes\n");}else {printf("No\n");}}return 0;
}

或者这样写 

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 20010;int n, m;
int p[N];
int find(int x) {if (p[x] != x)p[x] = find(p[x]);return p[x];
}
int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) p[i] = i;while (m--) {int a, b;scanf("%d%d", &a, &b);p[find(a)] = find(b);//合并 a->b}scanf("%d,&m");while (m--) {int a, b;scanf("%d%d", &a, &b);if (find(a) == find(b))puts("yes");else puts("no");}return 0;}

 

#include<iostream>
using namespace std;const int N = 10010;int n, m;
int p[N];int find(int x) {if (p[x] != x)p[x] = find(p[x]);return p[x];
}
int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) p[i] = i;char op[2];//读入操作的字符串  因为字符串后面有'\0'所以要存多一位while (m--) {int a, b;scanf("%s%d%d",&op ,&a, &b);if(*op=='M')p[find(a)] = find(b);//合并else {if (find(a) == find(b)) {puts("Yes");}else {puts("No");}}}return 0;
}

#include<iostream>
using namespace std;
const int N = 10010;int n, m;
int p[N], s[N];int find(int x) {if (p[x] != x)p[x] = find(p[x]);return p[x];
}
int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) p[i] = i, s[i] = 1;while (m--){char op[3];int a, b;scanf("%s", &op);if (*op == 'C') {scanf("%d%d", &a, &b);a = find(a), b = find(b);if (a != b) {//如果相等证明他们在同一个祖先中s[b] += s[a];p[a] = b;}else if (*op == 'Q1') {scanf("%d%d", &a, &b);if (find(a) == find(b)) {puts("Yes\n");}else {puts("No\n");}}else {scanf("%d", &a);printf("%d\n", s[find(a)]);}}}return 0;
}

 

相关文章:

图论-并查集

并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题.一些常见的用途有求连通子图,求最小生成树Kruskal算法和最近公共祖先(LCA)等. 并查集的基本操作主要有: .1.初始化 2.查询find 3.合并union 一般我们都会采用路径压缩 这样…...

redis-学习笔记(Jedis 通用命令)

flushAll 清空全部的数据库数据 jedis.flushAll();set & get set 命令 get 命令 运行结果展示 exists 判断该 key 值是否存在 当 redis 中存在该键值对时, 返回 true 如果键值对不存在, 返回 false keys 获取所有的 key 值 参数是模式匹配 *代表匹配任意个字符 _代表匹配一…...

C语言:高精度乘法

P1303 A*B Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 第一次画图&#xff0c;略显简陋。 由图可以看出c的小标与x,y下标的关系为x的下标加上y的下标再减一。 由此得到&#xff1a; c [ i j - 1 ] x [ i ] * y [ j ]x #include<stdio.h> #include<st…...

UE4 Niagara学习笔记

需要在其他发射器的同一个粒子位置发射其他粒子就用Spawn Particles from other Emitter 把发射器名字填上去即可 这里Move to Nearest Distance Field Subface GPU&#xff0c;可以将生成的Niagara附着到最近的物体上 使用场景就是做的火苗附着到物体上...

多维时序 | Matlab实现GA-LSTM-Attention遗传算法优化长短期记忆神经网络融合注意力机制多变量时间序列预测

多维时序 | MATLAB实现BWO-CNN-BiGRU-Multihead-Attention多头注意力机制多变量时间序列预测 目录 多维时序 | MATLAB实现BWO-CNN-BiGRU-Multihead-Attention多头注意力机制多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 多维时序 | Matlab实…...

LeetCode205. Isomorphic Strings

文章目录 一、题目二、题解 一、题目 Given two strings s and t, determine if they are isomorphic. Two strings s and t are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character wh…...

Event Driven设计模式

EDA&#xff08;Event-Driven Architecture&#xff09;是一种实现组件之间松耦合、易扩展的架构方式。一个最简单的EDA设计需要包含如下几个组件&#xff1a; Events&#xff1a;需要被处理的数据。一个Event至少包含两个属性&#xff0c;类型和数据&#xff0c;类型决定了Eve…...

PostgreSql 设置自增字段

一、概述 序列类型是 PostgreSQL 特有的创建一个自增列的方法。包含 smallserial、serial和 bigserial 类型&#xff0c;它们不是真正的类型&#xff0c;只是为了创建唯一标识符列而存在的方便符号。其本质也是调用的序列&#xff0c;序列详情可参考&#xff1a;《PostgreSql 序…...

什么是泊松图像混合

泊松图像混合&#xff08;Poisson Image Editing&#xff09;的原理基于泊松方程。该方法旨在保持图像中的梯度一致性&#xff0c;从而在图像编辑中实现平滑和无缝的混合。以下是泊松图像混合的基本原理和公式&#xff1a; 泊松方程 泊松方程是一个偏微分方程&#xff0c;通常…...

OpenAI 承认 ChatGPT 最近确实变懒,承诺修复问题

文章目录 一. ChatGPT 指令遵循能力下降引发用户投诉1.1 用户抱怨回应速度慢、敷衍回答、拒绝回答和中断会话 二. OpenAI 官方确认 ChatGPT 存在问题&#xff0c;展开调查三. OpenAI 解释模型行为差异&#xff0c;回应用户质疑四. GPT-4 模型变更受人事动荡和延期影响 一. Chat…...

创作活动(四十九)———低代码:美味膳食或垃圾食品?

#低代码&#xff1a;美味膳食或垃圾食品&#xff1f;# 一、什么是低代码 低代码是一种开发方法&#xff0c;通过可视化界面和少量的编码&#xff0c;使开发者能够快速构建应用程序。它的目标是提高开发效率、降低开发成本&#xff0c;并支持快速迭代和敏捷开发。 二、低代码的…...

【DL-TensorFlow遇错】TensorFlow中遇错合集

TensorFlow中遇错合集 一、AttributeError: module tensorflow has no attribute placeholder二、RuntimeError: tf.placeholder() is not compatible with eager execution. 一、AttributeError: module tensorflow has no attribute placeholder 错误原因 tensorflow版本问…...

pymysql代替mysqlclient,解决mysqlclient因版本不兼容无法安装成功而无法连接mysql的问题

pymysql代替mysqlclient&#xff0c;解决mysqlclient因版本不兼容无法安装成功而无法连接mysql的问题 原因&#xff1a;版本或者环境兼容问题&#xff0c;导致如centos或者其他Linux无法安装mysqlclient模块 解决办法&#xff1a;安装pymysql作为替代 在Django中连接MySQL数…...

uni-app 设置当前page界面进入直接变为横屏模式

首先 我们打开项目的 manifest.json 在左侧导航栏中找到 源码视图 然后找到 app-plus 配置 在下面加上 "orientation": [//竖屏正方向"portrait-primary",//竖屏反方向"portrait-secondary",//横屏正方向"landscape-primary",//横屏…...

Mysql的多表联合查询

内连接 隐式内连接 select column from tb1,tb2 where 条件; 显示内连接 关键字&#xff1a;[inner] join on 显示内连接与外连接的不同是新增的关键字&#xff0c;inner join 以及 使用on 替换了where select column from tb1 [inner] join tb2 on 条件; 外连接 左外…...

Linux上使用Python的requests库进行HTTP请求

在Linux上使用Python的requests库进行HTTP请求是一种非常方便和高效的方式。requests库是一个第三方库&#xff0c;用于发送HTTP请求并获取响应。下面是一个简单的示例&#xff0c;演示如何使用requests库发送GET请求并获取响应。 首先&#xff0c;你需要安装requests库。你可…...

图像处理领域的应用

图像处理领域的应用 文章目录 图像处理领域的应用1.图像类型2.图像转换3.彩色图像表示模式4.图像变换5.图像增强 1.图像类型 #mermaid-svg-x6mNS3Y1YkPvWUsQ {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-x6mNS3Y1…...

MySQL笔记-第18章_MySQL8其它新特性

视频链接&#xff1a;【MySQL数据库入门到大牛&#xff0c;mysql安装到优化&#xff0c;百科全书级&#xff0c;全网天花板】 文章目录 第18章_MySQL8其它新特性1. MySQL8新特性概述1.1 MySQL8.0 新增特性1.2 MySQL8.0移除的旧特性 2. 新特性1&#xff1a;窗口函数2.1 使用窗口…...

C语言—每日选择题—Day46

第一题 1. 下列程序段的输出结果是&#xff08;&#xff09; #include <stdio.h> int main() {int x 1,a 0,b 0;switch(x) {case 0: b;case 1: a;case 2: a;b;}printf("a%d,b%d\n", a, b);return 0; } A&#xff1a;a2,b1 B&#xff1a;a1,b1 C&#xf…...

flex布局,换行的元素上下设置间距

要生成的效果图如下&#xff1a; display:flexflex-direction: row;flex-wrap: wrap;当我们使用弹性盒子布局后&#xff0c;默认元素是没有外边距的&#xff0c;紧挨着样式就有点丑&#xff0c;如果想使换行后&#xff0c;元素的外边距有个距离&#xff0c;可以用如下方法解决…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

7种分类数据编码技术详解:从原理到实战

在数据分析和机器学习领域&#xff0c;分类数据&#xff08;Categorical Data&#xff09;的处理是一个基础但至关重要的环节。分类数据指的是由有限数量的离散值组成的数据类型&#xff0c;如性别&#xff08;男/女&#xff09;、颜色&#xff08;红/绿/蓝&#xff09;或产品类…...