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

2024.3.2力扣每日一题——受限条件下可到达节点的数目

2024.3.2

      • 题目来源
      • 我的题解
        • 方法一 深度优先搜索
        • 方法二 并查集

题目来源

力扣每日一题;题序:2368

我的题解

方法一 深度优先搜索

使用深度优先搜索实现,在搜索过程中根据restricted进行截停。

时间复杂度:O(n)
空间复杂度:O(n)

int res=0;
public int reachableNodes(int n, int[][] edges, int[] restricted) {List<Integer>[] g=createTree(n,edges);boolean[] bRestricted=new boolean[n];for(int i:restricted){bRestricted[i]=true;}dfs(g,0,-1,bRestricted);return res;
}
public List<Integer>[] createTree(int n,int[][] edges){List<Integer>[] g=new ArrayList[n];for(int i=0;i<n;i++){g[i]=new ArrayList<>();}for(int[] t:edges){int from = t[0];int to = t[1];g[from].add(to);g[to].add(from);}return g;
}
public void dfs(List<Integer>[] g,int cur,int pre,boolean[] bRestricted){res++;for(int next:g[cur]){//防止循环遍历  并且不能是受限节点if(next!=pre&&!bRestricted[next])dfs(g,next,cur,bRestricted);}
}
方法二 并查集

如果忽略受限的点,树就会变成若干个连通块,要计算的就是 0号点所在连通块的大小。
因此,可以用并查集来不断地将点集进行合并,依次考虑每一条边,如果边上两个点都没有受限,那么合并这两个点的所在集合,否则跳过该边。最终查询 0号点所在连通块的大小即可。

时间复杂度:O(n×α(n)),其中 n 是无向树中点的个数,α是反阿克曼函数。使用路径压缩和按秩合并优化后的并查集,单次查询和合并操作的时间复杂度是 O(α(n)),通常比较小,可以忽略。
空间复杂度:O(n)

public int reachableNodes(int n, int[][] edges, int[] restricted) {boolean[] bRestricted=new boolean[n];for(int i:restricted){bRestricted[i]=true;}UF uf=new UF(n);for(int[] v:edges){//如果起始和结束节点有一个是受限的节点,则不合并if(bRestricted[v[0]]||bRestricted[v[1]]){continue;}uf.union(v[0],v[1]);}return uf.getCount();
}
class UF{private int count;private int parent[];public UF(int n){count=n;parent=new int[n];for (int i = 0; i < n; i++) {parent[i]=i;}}public void union(int p,int q){int parentP=find(p);int parentQ=find(q);if (parentP==parentQ)return;parent[parentQ]=parentP;count--;}public boolean isConnection(int p,int q){int parentP=find(p);int parentQ=find(q);return parentP==parentQ;}public int find(int x){if(parent[x]!=x){parent[x]=find(parent[x]);//路径压缩}return parent[x];}public int getCount(){int cnt=0;//找0所在的集合int rt=find(0);for(int i=0;i<parent.length;i++){if(rt==find(i))cnt++;}return cnt;}
}

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

相关文章:

2024.3.2力扣每日一题——受限条件下可到达节点的数目

2024.3.2 题目来源我的题解方法一 深度优先搜索方法二 并查集 题目来源 力扣每日一题&#xff1b;题序&#xff1a;2368 我的题解 方法一 深度优先搜索 使用深度优先搜索实现&#xff0c;在搜索过程中根据restricted进行截停。 时间复杂度&#xff1a;O(n) 空间复杂度&#…...

在云端遇见雨云:一位服务器寻觅者的指南

引言&#xff1a;寻觅一座云端归宿 当我踏入数字世界的边缘&#xff0c;带着对网络的探索与期待&#xff0c;我迫切需要一座安全可靠的数字栖息地。云计算技术正如一场魔法般的变革&#xff0c;而在这片广袤的云端中&#xff0c;雨云就像是一位友善的向导&#xff0c;引领我穿越…...

Pygame基础10-物理模拟

PyMunk PyMunk是一个模拟物理的库。 注意&#xff0c;PyMunk只是进行物理模拟&#xff0c;不包含可视化的功能。如果需要可视化&#xff0c;可使用pygame等库。 可用pip安装pymunk pip install pymunk pymunk中的概念&#xff1a; space&#xff1a; 物理空间。 包含gravity 模…...

蓝桥杯 --- 日期问题模板

目录 1.如何判断闰年 2.如何遍历当前年份的每一天 3.如果想要输出某一年某一天到某一年某一天之间一共有多少天。 4.精确到具体周几到周几的问题分析 5.如何直接通过一层for循环枚举年月日 习题&#xff1a; 蓝桥杯竞赛特别喜欢考日期问题&#xff0c;今天给大家分享一下…...

Java 处理Mysql获取树形的数据

Mysql数据&#xff1a; 代码如下&#xff1a; Entity&#xff1a; Data Accessors(chain true) public class Region {private BigInteger id;//名称private String name;//父idprivate BigInteger parentId;private List<Region> children;private Integer createTim…...

前端三剑客 —— CSS ( 坐标问题 、定位问题和图片居中 )

前期内容回顾&#xff1a; 1.常见样式 text-shadow x轴 y轴 阴影的模糊程度 阴影的颜色 box-shadow border-radio 实现圆角 margin 内边距 padding 外边距 background 2.特殊样式 媒体查询&#xff1a;media 自定义字体&#xff1a;font-face { font-family:自定义名称&#…...

向量数据库 | AI时代的航道灯塔

向量数据库 | AI时代的航道灯塔 什么是向量检索服务拍照搜商品 你使用过向量数据库吗&#xff1f;使用体验&#xff1f;为什么向量数据库能借由大模型引起众多关注向量数据库在当前AI热潮中是昙花一现&#xff0c;还是未来AI时代的航道灯塔&#xff1f; 今天的话题主要是讨论向…...

Linux中的conntrack命令深入解析

在Linux网络管理和监控领域&#xff0c;conntrack命令是一个强大的工具&#xff0c;它提供了对netfilter连接跟踪系统的直接访问&#x1f50d;。这篇文章将深入探讨conntrack的由来、底层原理、参数意义&#xff0c;以及其常见用法&#xff0c;并对返回结果的每个字段进行详细解…...

反截屏控制技术如何防止信息通过手机拍照泄漏?

反截屏控制技术为企业数据安全提供了重要的防护措施。通过以下几点&#xff0c;有效阻止了信息通过拍照等方式的泄漏&#xff1a; 反截屏控制开启&#xff0c;用户启动截屏操作时&#xff0c;允许非涉密内容截屏操作&#xff0c;但所有涉密内容窗口会自动隐藏&#xff0c;防止涉…...

0.k8s简介

目录 k8s是什么 k8s不是什么 云原生 微服务 整体式架构与微服务架构 微服务的特性 微服务的优势 k8s是什么 Kubernetes 是一个可移植、可扩展的开源平台&#xff0c;用于管理容器化的工作负载和服务&#xff0c;可促进声明式配置和自动化。 Kubernetes 拥有一个庞大且快…...

VScode 集成终端设置默认打开当前文件夹 mac系统

一.快捷键设置 搜索 openInIntegratedTerminal 如图&#xff1a; 二.设置cmd 默认打开位置 点击设置 搜索 ntegrated:cwd 如下图&#xff1a; 三.查看ip 快捷指令&#xff1a; ipconfig getifaddr en0...

HDLbits 刷题 -- Alwaysblock2

学习&#xff1a; For hardware synthesis, there are two types of always blocks that are relevant: Combinational: always (*)Clocked: always (posedge clk) Clocked always blocks create a blob of combinational logic just like combinational always blocks, but…...

一、Docker部署GitLab(详细步骤)

Docker部署GitLab&#xff08;详细步骤&#xff09; 一、拉取镜像二、启动容器三、修改配置四、修改密码五、浏览器访问 一、拉取镜像 docker安装教程&#xff1a;https://qingsi.blog.csdn.net/article/details/131270071 docker pull gitlab/gitlab-ce:latest二、启动容器 …...

Vue3 Ajax(axios)

Vue 版本推荐使用 axios 来完成 ajax 请求。 安装方法 使用 cdn: <script src"https://unpkg.com/axios/dist/axios.min.js"></script> 使用 npm: $ npm install axios GET 方法 我们可以简单的读取 JSON 数据&#xff1a; const app {data() {r…...

正则表达式引擎库汇合

1.总览表格 一些正则表达式库的对比 index库名编程语言说明代码示例编译指令1Posix正则C语言是C标准库中用于编译POSIX风格的正则表达式库 posix-re.cgcc posix-re.c 2PCRE库C语言提供类似Perl语言的一个正则表达式引擎库。 一般系统上对应/usr/lib64/libpcre.so这个库文件&am…...

eBay买家号注册下单容易死号?是什么原因导致?

随着电子商务的迅猛发展&#xff0c;跨境电商平台eBay日益成为众多消费者和商家的首选。然而&#xff0c;自去年下半年以来&#xff0c;eBay推出的新规则给买家号的注册带来了前所未有的挑战。许多新用户反映&#xff0c;在注册eBay买家号后&#xff0c;往往遭遇刚注册就被冻结…...

【Linux】-进程知识铺垫①计算机硬件的组织:冯诺依曼体系结构详细解读②关于操作系统对软硬件及用户的意义

目录 ​编辑 1.关于计算机的体系结构 1.1 冯诺依曼体系结构的诞生 2.冯诺依曼体系结构 2.1 cpu:运算器&#xff1a;更多的是让cpu具有特殊的数据计算功能&#xff1a; 2.2 控制器 2.3输入设备 2.4输出设备 3.计算机各个硬件设备之间的关系 4.内存与计算机效率 5.关于为什么总说…...

让ECC升级S/4HANA一步到位的“全面升级方案包”

SAP最新一代商务套件S/4HANA比ECC系统拥有更高性能的存储数据库HANA、更个性化的Fiori用户界面设计系统&#xff0c;能够大大提升系统效率&#xff0c;带来便捷、高效、良好的用户体验。但企业原先使用的ECC系统里面保存了积累多年的关键流程和数据&#xff0c;让企业面对系统升…...

AutoGluon

官网 amazon (base) PS C:\Users\gg葱> conda env list # conda environments: # pytorch1 C:\Users\gg葱\.conda\envs\pytorch1 base * D:\ANCDD:\Documents\LMm\env\pytorch2(base) PS C:\Users\gg葱> conda create --prefixD:/Doc…...

【网站项目】少儿编程管理系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

土建施工员考试:建筑施工技术重点知识有哪些?

《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目&#xff0c;核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容&#xff0c;附学习方向和应试技巧&#xff1a; 一、施工组织与进度管理 核心目标&#xff1a; 规…...