力扣--并查集547.省份数量

思路分析:
- 首先定义变量
fa用于记录并查集,以及城市数量n。 - 定义了并查集的两个函数,
find用于查找节点的根节点,togother用于合并两个节点所在的集合。 - 在公共函数
findCircleNum中,初始化并查集,然后遍历 isConnected 数组,将相连的城市进行合并。 - 最后使用 visited 数组记录每个城市是否已经被访问过,然后统计省份的数量并返回。
class Solution {int fa[201]; // 并查集数组,用于记录节点的父节点int n; // 城市数量// 定义并查集的查找函数,用于查找节点 x 的根节点(即所属集合的代表节点)int find(int x) {// 如果节点 x 的父节点就是它自己,则返回 xif (fa[x] == x)return x;// 否则,递归地查找 x 的父节点,并返回结果elsereturn find(fa[x]);}// 定义并查集的合并函数,用于合并节点 x 和节点 y 所在的两个集合void togother(int x, int y) {// 将节点 x 所在集合的根节点设为节点 y 所在集合的根节点fa[find(x)] = find(y);}public:// 定义一个公共函数,用于计算省份的数量int findCircleNum(vector<vector<int>>& isConnected) {// 获取城市数量n = isConnected.size();// 初始化并查集,将每个节点的父节点设为它自己for (int i = 0; i < n; i++)fa[i] = i;// 遍历 isConnected 数组,将相连的城市进行合并for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {if (isConnected[i][j] == 1)togother(i, j);}}// 使用 visited 数组记录每个城市是否已经被访问过vector<bool> visited(n, false);int count = 0; // 记录省份的数量// 遍历每个城市,对于每个城市,如果其所在集合的根节点尚未被访问过,则将其标记为已访问,并增加省份数量for (int i = 0; i < n; i++) {if (visited[find(i)] == false) {count++;visited[find(i)] = true;}}// 返回省份的数量return count;}
};
相关文章:
力扣--并查集547.省份数量
思路分析: 首先定义变量 fa 用于记录并查集,以及城市数量 n。定义了并查集的两个函数,find 用于查找节点的根节点,togother 用于合并两个节点所在的集合。在公共函数 findCircleNum 中,初始化并查集,然后遍…...
leetcode35-Search Insert Position
排序数组搜索某个元素,这种思维一定要往二分法上靠 public class searchInsertPosition{public static void main(String[] args) {int arr[] {1,3,5,6};System.out.println(getIndex(arr,2));}public static int getIndex(int[] arr,int target) {int start 0;i…...
API 接口渗透测试
1 API 接口介绍 1.1 RPC(远程过程调用) 远程过程调用(英语:Remote Procedure Call,缩写为 RPC)是一个计算机通信协议。该协议允许运行于一台计算机的程序调用另一台计算机的子程序,而程序员无…...
oracle 19c单机版本补丁升级
文章目录 一、补丁包概述二、备份opatch三、替换高版本opatch四、打DB补丁1、关闭数据库2、关闭监听3、解压补丁4、冲突检测5、补丁空间检查6、执行补丁升级7、将更新内容加载到数据库8、最后查看数据库版本9、卸载补丁包 一、补丁包概述 补丁升级包 链接:https://…...
推荐系统的未来:大模型驱动的个性化推荐技术与挑战
推荐系统的未来:大模型驱动的个性化推荐技术与挑战 1. 背景介绍 推荐系统是现代互联网服务中不可或缺的一部分,它通过分析用户的历史行为和偏好,为用户提供个性化的内容推荐,从而提高用户体验和满意度。随着大数据、机器学习和人…...
Allegro许可管理工具
在数字化时代,软件许可管理成为企业面临的挑战之一。如何确保软件的合规使用、优化资源配置并降低运营成本是企业关注的焦点。Allegro许可管理工具作为一款强大的管理工具,为企业提供了全面、高效的解决方案。本文将深入探讨Allegro许可管理工具的卓越实…...
React函数组件Hook
问题: 相对于类组件, 函数组件的编码更简单, 效率也更高, 但函数组件不能有state (旧版) 解决: React 16.8版本设计了一套新的语法来让函数组件也可以有state Hook 是 React 16.8 的新增特性。它可以让你在不编写 class 的情况下使用 state 以及其他的 React 特性 Hook也叫钩子…...
【FinalShell】远程连接 Linux 工具 FinalShell 的使用:查看 AI 语言大模型对话实时日志
一、查看 APP 实时 AI 问答消息的 websocket 类型日志 (1)Linux 模板命令配置 Linux 命令:查看 AI 语言大模型结合向量数据库的实时问答消息日志 ① 测试环境 FinalShell 命令模板 【Linux 命令标题】[Test_APP] today tail:webs…...
ARM Coresight 系列文章 11.1 -- CoreSight Cortex-M33 CTI 详细介绍】
请阅读【ARM Coresight SoC-400/SoC-600 专栏导读】 文章目录 CTI 的工作原理CTI 主要特点CTI的使用场景CTI 的工作原理 CTI 允许不同的调试和追踪组件之间基于特定事件进行交互。例如,当一个断点被命中时,CTI 可以用来触发内存的追踪捕捉或者外部仪器的行为,反之亦然。这种…...
Linux常用操作命令(清单快查版)
Linux常用操作命令,今日先给出快查清单,后续出带命令参数及不同OS的区别语法的相关示例 1. 文件与目录操作 命令描述ls列出目录内容cd切换目录pwd显示当前工作目录mkdir创建目录rmdir删除空目录cp复制文件或目录mv移动或重命名文件或目录rm删除文件或目…...
[C语言]结构体、位段、枚举常量、联合体
目录 结构体 结构体的使用方法 结构体所占用的大小 位段 位段的使用方法 位段所占用的大小 枚举常量 枚举常量的使用方法 枚举常量的优势 联合体 联合体的使用方法 结构体 结构体的使用方法 结构体是一些值的集合,我们可以定义一个结构体,里…...
LangChain核心模块 Retrieval——文档加载器
Retrieval 许多LLM申请需要用户的特定数据,这些数据不属于模型训练集的一部分,实现这一目标的主要方法是RAG(检索增强生成),在这个过程中,将检索外部数据,然后在执行生成步骤时将其传递给LLM。 LangChain 提供…...
力扣爆刷第104天之CodeTop100五连刷6-10
力扣爆刷第104天之CodeTop100五连刷6-10 文章目录 力扣爆刷第104天之CodeTop100五连刷6-10一、15. 三数之和二、53. 最大子数组和三、912. 排序数组四、21. 合并两个有序链表五、1. 两数之和 一、15. 三数之和 题目链接:https://leetcode.cn/problems/3sum/descrip…...
Docker操作基础命令
注意:以下命令在特权模式下进行会更有效! 进入特权模式 sudo -ssudo su拉取镜像 sudo docker pull [镜像名] # sudo docker pull baiduxlab/sgx-rust:2004-1.1.3进入容器 端口开启服务: sudo docker start 3df9bf5dbd0c进入容器…...
穿越地心:3D可视化技术带你领略地球内部奇观
在广袤无垠的宇宙中,地球是一颗充满生机与奥秘的蓝色星球。我们每天都生活在这颗星球上,感受着它的温暖与恩赐,却往往忽略了它深邃的内部世界。 想象一下,你能够穿越时空,深入地球的核心,亲眼目睹那些亿万年…...
蓝桥杯刷题_day1_回文数_水仙花数_进制转换
文章目录 特殊的回文数回文数水仙花数十六进制转八进制_n次 特殊的回文数 问题描述 123321是一个非常特殊的数,它从左边读和从右边读是一样的。 输入一个正整数n, 编程求所有这样的五位和六位十进制数,满足各位数字之和等于n 。 解题…...
jmeter接口导入方式
curl直接导入 1、操作页面后,F12查看接口,右击接口-copy-copy as cURL 2、jmeter 工具-import from cURL,粘贴上面复制的curl 根据接口文档导入 1、接口文档示例如下: Path: /api/jobs/xps/exec Method…...
设计模式(行为型设计模式——状态模式)
设计模式(行为型设计模式——状态模式) 状态模式 基本定义 对有状态的对象,把复杂的“判断逻辑”提取到不同的状态对象中,允许状态对象在其内部状态发生改变时改变其行为。 模式结构 Context(环境类)&…...
【Flutter学习笔记】10.3 组合实例:TurnBox
参考资料:《Flutter实战第二版》 10.3 组合实例:TurnBox 这里尝试实现一个更为复杂的例子,其能够旋转子组件。Flutter中的RotatedBox可以旋转子组件,但是它有两个缺点: 一是只能将其子节点以90度的倍数旋转二是当旋转…...
性能测试入门 —— 什么是性能测试PTS?
性能测试PTS(Performance Testing Service)是一款简单易用,具备强大的分布式压测能力的SaaS压测平台。 PTS可以模拟复杂的业务场景,并快速精准地调度不同规模的流量,同时提供压测过程中多维度的监控指标和日志记录。您…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...
pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决
问题: pgsql数据库通过备份数据库文件进行还原时,如果表中有自增序列,还原后可能会出现重复的序列,此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”,…...
向量几何的二元性:叉乘模长与内积投影的深层联系
在数学与物理的空间世界中,向量运算构成了理解几何结构的基石。叉乘(外积)与点积(内积)作为向量代数的两大支柱,表面上呈现出截然不同的几何意义与代数形式,却在深层次上揭示了向量间相互作用的…...
归并排序:分治思想的高效排序
目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法,由约翰冯诺伊曼在1945年提出。其核心思想包括: 分割(Divide):将待排序数组递归地分成两个子…...
【java面试】微服务篇
【java面试】微服务篇 一、总体框架二、Springcloud(一)Springcloud五大组件(二)服务注册和发现1、Eureka2、Nacos (三)负载均衡1、Ribbon负载均衡流程2、Ribbon负载均衡策略3、自定义负载均衡策略4、总结 …...
算法250609 高精度
加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...
