香港空间网站 备案/网络运营推广具体做什么工作
前言
这里记录一下陈菜菜的刷题记录,主要应对25秋招、春招
个人背景
211CS本+CUHK计算机相关硕,一年车企软件开发经验
代码能力:有待提高
常用语言:C++
系列文章目录
第59天 :第十一章:图论part05
`
文章目录
- 前言
- 系列文章目录
- 第59天 :第十一章:图论part05
- 一、今日任务
- 二、详细布置
- 并查集理论基础
- 模板
- 拓展
- 107. 寻找存在的路径
- 提示:
- 样例1:
- 思路
- 实战
- 总结
一、今日任务
● 并查集理论基础
● 寻找存在的路径
二、详细布置
并查集理论基础
并查集常用来解决连通性问题。
我们需要判断两个元素是否在同一个集合里的时候,我们就要想到用并查集。
并查集主要有两个功能:
将两个元素添加到一个集合中。
判断两个元素在不在同一个集合
模板
int n = 1005; // n根据题目中节点数量而定,一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}
// 并查集里寻根的过程
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (u == v) return ; // 如果发现根相同,则说明在一个集合,不用两个节点相连直接返回father[v] = u;
}
通过模板,我们可以知道,并查集主要有三个功能。
1.寻找根节点,函数:find(int u),也就是判断这个节点的祖先节点是哪个
2.将两个节点接入到同一个集合,函数:join(int u, int v),将两个节点连在 同一个根节点上
3.判断两个节点是否在同一个集合,函数:isSame(int u, int v),就是判断两个节点是不是同一个根节点
拓展
在「路径压缩」讲解中,我们知道如何靠压缩路径来缩短查询根节点的时间。
其实还有另一种方法:按秩(rank)合并。
rank表示树的高度,即树中结点层次的最大值。
int n = 1005; // n根据题目中节点数量而定,一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构
vector<int> rank = vector<int> (n, 1); // 初始每棵树的高度都为1// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;rank[i] = 1; // 也可以不写}
}
// 并查集里寻根的过程
int find(int u) {return u == father[u] ? u : find(father[u]);// 注意这里不做路径压缩
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (rank[u] <= rank[v]) father[u] = v; // rank小的树合入到rank大的树else father[v] = u;if (rank[u] == rank[v] && u != v) rank[v]++; // 如果两棵树高度相同,则v的高度+1,因为上面 if (rank[u] <= rank[v]) father[u] = v; 注意是 <=
}
107. 寻找存在的路径
题目链接:力扣107
文章讲解:代码随想录
给定一个包含 n 个节点的无向图中,节点编号从 1 到 n (含 1 和 n )。
你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。
输入:
第一行包含两个正整数 N 和 M,N 代表节点的个数,M 代表边的个数。
后续 M 行,每行两个正整数 s 和 t,代表从节点 s 与节点 t 之间有一条边。
最后一行包含两个正整数,代表起始节点 source 和目标节点 destination。
输出:
输出一个整数,代表是否存在从节点 source 到节点 destination 的路径。如果存在,输出 1;否则,输出 0。
提示:
数据范围:
1 <= M, N <= 100
样例1:
输入:
5 4
1 2
1 3
2 4
3 4
1 4
输出:
1
思路
这题模板题。
实战
#include<iostream>
#include<vector>
using namespace std;
int n = 105;
vector<int> father = vector<int> (n, 0); void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (u == v) return ; // 如果发现根相同,则说明在一个集合,不用两个节点相连直接返回father[v] = u;
}int main(){int n,m,s,t;cin>>n>>m;init();for(int i=0;i<m;i++){cin>>s>>t;join(s,t);}int begin,end;cin>>begin>>end;if(isSame(begin,end))cout<<1<<endl;elsecout<<0<<endl;
}
总结
今天主要学习了并查集的一系列操作,感觉并查集很好理解,模板记忆一下。主要是压缩路径。
加油,坚持打卡的第59天。
相关文章:

代码训练营 day59|并查集
前言 这里记录一下陈菜菜的刷题记录,主要应对25秋招、春招 个人背景 211CS本CUHK计算机相关硕,一年车企软件开发经验 代码能力:有待提高 常用语言:C 系列文章目录 第59天 :第十一章:图论part05 文章目录…...

Node.js——fs模块-路径补充说明
1、相对路径: ./座右铭.txt 当前目录下的座右铭.txt座右铭.txt 等效于上面的写法../座右铭.txt 当前目录的上一级目录中的座右铭.txt 2、绝对路径 D:/Program File Windows系统下的绝对路径/usr/bin Linux系统…...

华为ENSP--ISIS路由协议
项目背景 为了确保资源共享、办公自动化和节省人力成本,公司E申请两条专线将深圳总部和广州、北京两家分公司网络连接起来。公司原来运行OSFP路由协议,现打算迁移到IS-IS路由协议,张同学正在该公司实习,为了提高实际工作的准确性和…...

论软件可靠性设计及其应用
摘要 2023 年 3 月,我所在的公司承接了某智慧加油站平台的建设工作。该项目旨在帮助加油站提升运营效率、降低运营成本和提高销售额。我在该项目中担任系统架构设计师,负责整个项目的架构设计工作。 本文结合我在该项目中的实践,详细论述了…...

Android中桌面小部件framework层使用到的设计模式
在Android中,桌面小部件(App Widget)的Framework层采用了多种设计模式,以实现模块化、可维护性和高效的交互。 以下是Android桌面小部件Framework层中常用的设计模式及其具体应用: 1. 观察者模式(Observe…...

【JavaEE进阶】HTML
本节⽬标 认识 HTML 的基本结构, 学习常⽤的 HTML 标签. 一 HTML基础 1.什么是HTML HTML(Hyper Text Markup Language), 超⽂本标记语⾔. 超⽂本: ⽐⽂本要强⼤. 通过链接和交互式⽅式来组织和呈现信息的⽂本形式. 不仅仅有⽂本, 还可能包含图⽚, ⾳频, 或者⾃已经审阅过它…...

ElasticSearch 添加IK分词器
ElasticSearch 添加IK分词器 前言一、IK分词器的算法二、Ik分词器的下载安装(Winows 版本)三、Ik分词器的下载安装(Linux 版本)四、验证测试(postman工具)测试 ik_smart 分词算法测试 ik_max_word 分词算法…...

可视化建模与UML《顺序图实验报告》
旷野的规则是永不回头。 一、实验目的: 1、熟悉顺序图的构件事物。 2、熟悉发送者与接受者的关系 3、熟练掌握描绘顺序图 4、加深对顺序图的理解和应用能力 二、实验环境: window7 | 10 | 11 EA15 三、实验内容: 据如下描述绘制顺序图&…...

Mac的极速文件搜索工具,高效管理文件
Mac的资源管理可以说是许多转Mac的朋友用不明白的一点了,访达怎么用,文件怎么找,为什么找不到,非常的头大 All作为Mac上的极速文件搜索管理工具,有效的为文件查找困难的用户解决难题 基于极速搜索引擎,快…...

公开仓库改私有再配置公钥后Git拉取仍需要输入用户名的问题
问题描述:git拉取私有仓库需要输入用户名和密码 我之前写了一个脚本用来定时自动拉取远程仓库更新本地仓库,后来将这个远程仓库改成私有后执行脚本就会需要输入用户名和密码。 [rootLH2020 ~]# ./sync_repo.sh 正在从远程仓库拉取最新更改… Username f…...

工作流初始错误 泛微提交流程提示_泛微协同办公平台E-cology8.0版本后台维护手册(11)–系统参数设置
工作流初始错误 泛微提交流程提示_泛微协同办公平台E-cology8.0版本后台维护手册(11)–系统参数设置...-CSDN博客 工作流初始错误 泛微提交流程提示_泛微OA 工作流WebService接口使用说明 工作流初始错误 泛微提交流程提示_泛微OA 工作流WebService接口使用说明-CSDN博客 工作…...

window下安装rust 及 vscode配置
安装 安装mingw64 (c语言环境 选择posix-ucrt) ucrt:通用c运行时库配置mingw64/bin的路径到环境变量中在cmd窗口中输入命令 "gcc -v" 4. 下载Rust安装程序 安装 Rust - Rust 程序设计语言 5. 配置rustup和cargo目录 (cargo是包管…...

【数据结构】【线性表】单链表1—概念即创建(附C语言源码)
单链表的定义, 链表用链式存储的方式实现线性表,链表中每个结点元素中需要指向下一个结点的指针(有时候也要指向上一个结点的指针),链表中的每个结点指针只指向下一结点的被叫为单链表。 单链表的创建和初始化 先定…...

centos7的maven配置
首先进入conf配置文件夹下的setting.xml 要改两个地方 第一:设置镜像源 <mirror> <id>alimaven</id> <name>aliyun maven</name> <url>https://maven.aliyun.com/nexus/content/groups/public/</url> <mirrorOf>c…...

day57 图论章节刷题Part08(拓扑排序、dijkstra(朴素版))
拓扑排序-117. 软件构建 思路:拓扑排序是经典的图论问题。给出一个有向图,把有向图转成线性的排序就叫拓扑排序,拓扑排序也要检测有向图是否有环,即存在循环依赖的情况,因为这种情况是不能做线性排序的,所…...

【Steam登录】protobuf协议逆向
https://api.steampowered.com/IAuthenticationService/GetPasswordRSAPublicKey/v1 搜索 input_protobuf_encoded定位 input_protobuf_encoded的值就是 o s r.SerializeBody() o i.iI(s) 精准定位 打上条件断点:t ‘Authentication.GetPasswordRSAPublicKey…...

git 对已提交的说明进行编辑
如果提交代码的时候,对上次提交代码的说明不准确的话,例如 1、可以使用 git log 查看代码提交的记录; 2、使用 git commit --amend 命令对上次提交的说明进行编辑: 当显示上次提交的内容的时候,按下键盘 i 键即可编辑…...

CTF —— 网络安全大赛
前言 💻随着大数据、人工智能的发展,人们步入了新的时代,逐渐走上科技的巅峰。 ⚔科技是一把双刃剑,网络安全不容忽视,人们的隐私在大数据面前暴露无遗,账户被盗、资金损失、网络诈骗、隐私泄露ÿ…...

【大数据测试spark+kafka-详细教程(附带实例)】
大数据测试:Spark Kafka 实时数据处理与窗口计算教程 1. 概述1.1 大数据技术概述1.2 Apache Kafka 与 Spark 的结合 2. 技术原理与流程2.1 Kafka 简介2.2 Spark Streaming 简介2.3 数据流动与处理流程 3. 环境配置3.1 安装依赖项 4. 实例:实时数据处理与…...

如何为 GitHub 和 Gitee 项目配置不同的 Git 用户信息20241105
🎯 如何为 GitHub 和 Gitee 项目配置不同的 Git 用户信息 引言 在多个代码托管平台(如 GitHub 和 Gitee)之间切换时,正确管理用户信息至关重要。频繁使用不同项目时,若用户配置不当,可能会导致意外提交或…...

【Lucene】原理学习路线
基于《Lucene原理与代码分析完整版》,借助chatgpt等大模型,制定了一个系统学习Lucene原理的计划,并将每个阶段的学习内容组织成专栏文章,zero2hero 手搓 Lucene的核心概念和实现细节。 深入的学习和专栏计划,覆盖Lucen…...

Go语言的并发安全与互斥锁
线程通讯 在程序中不可避免的出现并发或者并行,一般来说对于一个程序大多数是遵循开发语言的启动顺序。例如,对于go语言来说,一般入口为main,main中依次导入import导入的包,并按顺序执行init方法,之后在按…...

SpringBoot框架在资产管理中的应用
3系统分析 3.1可行性分析 通过对本企业资产管理系统实行的目的初步调查和分析,提出可行性方案并对其一一进行论证。我们在这里主要从技术可行性、经济可行性、操作可行性等方面进行分析。 3.1.1技术可行性 本企业资产管理系统采用Spring Boot框架,JAVA作…...

ElasticSearch备考 -- 集群配置常见问题
一、集群开启xpack安全配置后无法启动 在配置文件中增加 xpack.security.enabled: true 后无法启动,日志中提示如下 Transport SSL must be enabled if security is enabled. Please set [xpack.security.transport.ssl.enabled] to [true] or disable security b…...

【UE5】一种老派的假反射做法,可以用于移动端,或对反射的速度、清晰度有需求的地方
没想到大家这篇文章呼声还挺高 这篇文章是对它的详细实现,建议在阅读本篇之前,先浏览一下前面的文章,以便更好地理解和掌握内容。 这种老派的假反射技术,适合用于移动端或对反射效果的速度和清晰度有较高要求的场合。该技术通过一…...

FasterNet中Pconv的实现、效果与作用分析
发表时间:2023年3月7日 论文地址:https://arxiv.org/abs/2303.03667 项目地址:https://github.com/JierunChen/FasterNet FasterNet-t0在GPU、CPU和ARM处理器上分别比MobileViT-XXS快2.8、3.3和2.4,而准确率要高2.9%。我们的大型…...

QToolbar工具栏下拉菜单不弹出有小箭头
这里说了怎么弹出:Qt 工具栏QToolBar添加带有弹出菜单的QAction_qt如何将action添加到工具栏-CSDN博客 然后如果你是在UI里面建立的action,并拖到了toolbar,并在代码中设置菜单,例如: ui->mytoolbar->setMenu(…...

w025基于SpringBoot网上超市的设计与实现
🙊作者简介:拥有多年开发工作经验,分享技术代码帮助学生学习,独立完成自己的项目或者毕业设计。 代码可以查看文章末尾⬇️联系方式获取,记得注明来意哦~🌹赠送计算机毕业设计600个选题excel文件࿰…...

深度学习在推荐系统中的应用
参考自《深度学习推荐系统》,用于学习和记录。 前言 (1)与传统的机器学习模型相比,深度学习模型的表达能力更强,能够挖掘(2)深度学习的模型结构非常灵活,能够根据业务场景和数据特…...

软考系统架构设计师论文:论面向对象的建模及应用
试题三 论面向对象的建模及应用 软件系统建模是软件开发中的重要环节,通过构建软件系统模型可以帮助系统开发人员理解系统、抽取业务过程和管理系统的复杂性,也可以方便各类人员之间的交流。软件系统建模是在系统需求分析和系统实现之间架起的一座桥梁,系统开发人员按照软件…...