当前位置: 首页 > 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…...

基于C语言的数据结构--顺序表讲解及代码函数实现展示

本篇文章是数据结构的开篇&#xff0c;所以我们先来了解一下什么是数据结构。 什么是数据结构 数据结构是由“数据”和“结构”两个词组合而来&#xff0c;自然要以两个词分别去阐述。 首先&#xff0c;什么是数据&#xff1f;数据(data)是事实或观察的结果&#xff0c;是对客…...

(学习日记)2024.03.31:UCOSIII第二十八节:消息队列常用函数

写在前面&#xff1a; 由于时间的不足与学习的碎片化&#xff0c;写博客变得有些奢侈。 但是对于记录学习&#xff08;忘了以后能快速复习&#xff09;的渴望一天天变得强烈。 既然如此 不如以天为单位&#xff0c;以时间为顺序&#xff0c;仅仅将博客当做一个知识学习的目录&a…...

DLC原理解析及其优化思考

1. 引言 Discreet Log Contract (DLC) 是由麻省理工学院的Tadge Dryja在2018年提出的一套基于预言机的合约执行方案。DLC 允许两方根据预定义的条件进行有条件付款。各方确定可能的结果并进行预签名&#xff0c;并在预言机签署结果时使用这些预签名来执行支付。 因此&#xff…...

tigramite教程(七)使用TIGRAMITE 进行条件独立性测试

文章目录 概述1 连续数值变量1.1 ParCorr 偏相关&#xff08;ParCorr类&#xff09;1.2 鲁棒偏相关&#xff08;RobustParCorr&#xff09;非线性检验1.3 GPDC1.4 CMIknn 2a. 分类/符号时间序列2b. 混合分类/连续时间序列多变量X和Y的测试 概述 这个表格概述了 X ⊥ Y ∣ Z X\…...

【DevOps工具篇】使用Ansible部署Keycloak oauth2proxy 和 单点登录(SSO)设置

【DevOps工具篇】使用Ansible部署Keycloak oauth2proxy 和 单点登录(SSO)设置 目录 【DevOps工具篇】使用Ansible部署Keycloak oauth2proxy 和 单点登录(SSO)设置Ansible 基础知识部署 Keycloak创建 OIDC-客户端创建 oauth2proxy 部署顶级 Ansible PlaybookHost.iniplayboo…...

鸿蒙OS开发实例:【应用状态变量共享】

平时在开发的过程中&#xff0c;我们会在应用中共享数据&#xff0c;在不同的页面间共享信息。虽然常用的共享信息&#xff0c;也可以通过不同页面中组件间信息共享的方式&#xff0c;但有时使用应用级别的状态管理会让开发工作变得简单。 根据不同的使用场景&#xff0c;ArkT…...

C#清空窗体的背景图片

目录 一、涉及到的知识点 1.设置窗体的背景图 2.加载窗体背景图 3.清空窗体的背景图 二、 示例 一、涉及到的知识点 1.设置窗体的背景图 详见本文作者的其他文章&#xff1a;C#手动改变自制窗体的大小-CSDN博客 https://wenchm.blog.csdn.net/article/details/137027140…...

Qt 实现的万能采集库( 屏幕/相机/扬声器/麦克风采集)

【写在前面】 之前应公司需要&#xff0c;给公司写过一整套直播的库( 推拉流&#xff0c;编解码)&#xff0c;类似于 libobs。 结果后来因为没有相关项目&#xff0c;便停止开发&维护了。 不过里面很多有用的组件&#xff0c;然后也挺好用的&#xff0c;遂开源出来一部分。…...

将写好的打印机代码打包成jar包然后直接注册成windows服务,然后通过调用插件的接口地址将流传到接口实现解析并无需预览直接通过打印机直接打印PDF文件

实现文件流PDF不需要预览直接调用打印机打印实现方案就是&#xff0c;将写好的打印机代码打包成jar包然后直接注册成windows服务&#xff0c;然后通过调用插件的接口地址将流传到接口实现解析并无需预览直接通过打印机直接打印PDF文件。源码地址...

加密软件VMProtect教程:使用脚本-功能

VMProtect是新一代软件保护实用程序。VMProtect支持德尔菲、Borland C Builder、Visual C/C、Visual Basic&#xff08;本机&#xff09;、Virtual Pascal和XCode编译器。 同时&#xff0c;VMProtect有一个内置的反汇编程序&#xff0c;可以与Windows和Mac OS X可执行文件一起…...

湿地公园网站开发招标/营销型网站建设步骤

momis home链接:http://www.geocities.jp/momi619jp/来自 “ ITPUB博客 ” &#xff0c;链接&#xff1a;http://blog.itpub.net/39335/viewspace-351259/&#xff0c;如需转载&#xff0c;请注明出处&#xff0c;否则将追究法律责任。 转载于:http://blog.itpub.net/39335/vi…...

中色十二冶金建设有限公司网站/专业全网优化

TensorFlow - Softmax flyfish 公式 sigma(z)jezj∑Kk1ezksigma(z)jezj∑k1Kezk解释 K表示K维向量 类似一个向量里面有K个实数值&#xff0c;通过Softmax函数输出另一个向量&#xff0c;另一个向量也K个实数值&#xff0c;每一个实数都是0到1之间的数&#xff0c;并且它们的…...

郑州网站建设预订/湖南seo服务电话

本文大纲 我觉得很有必要讲述这个文章&#xff0c;进行数据处理的第一步就是Python数据读取。但是你可能没想到&#xff0c;在进行数据读取的同时&#xff0c;我们其实可以配合相关参数做很多事儿&#xff0c;这对于后续的数据处理都是极其有帮助。read_excel()函数和read_csv(…...

内容电商的网站如何做/桔子seo查询

mysql查询今天,昨天,近7天,近30天,本月,上一月数据最近项目中用到了查询当月数据记录的功能&#xff0c;最初的想法是在逻辑业务里构造好时间段进行查询&#xff0c;当写sql语句时感觉挺麻烦。所以就到网上搜索了一下&#xff0c;看看是不是能有简单的方法。果然&#xff0c;网…...

个人网站做企业网站/免费做网站

jquery的优秀的控件库 包括常用 messager dialog pannel tree 等控件 http://files.cnblogs.com/wangdetian168/jquery-easyui-1%5b1%5d.0.5.rar转载于:https://www.cnblogs.com/wangdetian168/archive/2010/09/26/jquery-kongjian.html...

信丰网站制作/网站统计工具有哪些

AQTime和MemProof都是AutomatedQA旗下的产品&#xff0c;AQTime比MemProof提供了更丰富强大的功能。该产品含有完整的性能和调试工具集&#xff0c;能够收集程序运行时关键的性能信息和内存/资源分配信息&#xff0c;并提交概要报告和详细报告&#xff0c;还提供所有的程序优化…...