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

每天一道leetcode:1466. 重新规划路线(图论中等广度优先遍历)

今日份题目:

n 座城市,从 0n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部决定重新规划路线,以改变交通拥堵的状况。

路线用 connections 表示,其中 connections[i] = [a, b] 表示从城市 ab 的一条有向路线。

今年,城市 0 将会举办一场大型比赛,很多游客都想前往城市 0 。

请你帮助重新规划路线方向,使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。

题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。

示例1

输入:n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
输出:3
解释:更改以红色显示的路线的方向,使每个城市都可以到达城市 0 。

示例2

输入:n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
输出:2
解释:更改以红色显示的路线的方向,使每个城市都可以到达城市 0 。

示例3

输入:n = 3, connections = [[1,0],[2,0]]
输出:0

提示

  • 2 <= n <= 5 * 10^4

  • connections.length == n-1

  • connections[i].length == 2

  • 0 <= connections[i][0], connections[i][1] <= n-1

  • connections[i][0] != connections[i][1]

题目思路

这道题我们使用bfs广度优先遍历。拿例1为例,我们只需要从0开始遍历,由于路径单向通行,故与这些点的连线都需要反向,除此之外,下边那条边直接找是无法从0走过去的,但还有条路需要反向,这时,我们引入反向图,在正向bfs的同时对反向图同样bfs,放入同一个队列中,这样就可以保证图中所有不满足条件的边都被记录下来了。

所谓反向图,就是将图中所有的路径反向,(i,j)处的值与(j,i)处的值交换。

代码

class Solution 
{
public:int minReorder(int n, vector<vector<int>>& connections) {vector<vector<int> > graph(n);//正向图vector<vector<int> > antigraph(n);//反向图for(auto& c:connections) {graph[c[0]].push_back(c[1]);//记录正向图antigraph[c[1]].push_back(c[0]);//记录反向图}int ans=0;int visited[100000]={0};visited[0]=1;queue<int> p;p.push(0);//bfswhile(!p.empty()) {//获取当前点信息int i=p.front();p.pop();//正向遍历搜寻结果for(int j=0;j<graph[i].size();j++){if(visited[graph[i][j]]==0) {visited[graph[i][j]]=1;//标记为已到达过ans++;//0向外能到达的点的路径就是需要反向的路径p.push(graph[i][j]);}}//反向遍历搜寻结果for(int j=0;j<antigraph[i].size();j++){if(visited[antigraph[i][j]]==0) {visited[antigraph[i][j]]=1;//标记为已到达过p.push(antigraph[i][j]);} }            }return ans;}
};

提交结果

 欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!

相关文章:

每天一道leetcode:1466. 重新规划路线(图论中等广度优先遍历)

今日份题目&#xff1a; n 座城市&#xff0c;从 0 到 n-1 编号&#xff0c;其间共有 n-1 条路线。因此&#xff0c;要想在两座不同城市之间旅行只有唯一一条路线可供选择&#xff08;路线网形成一颗树&#xff09;。去年&#xff0c;交通运输部决定重新规划路线&#xff0c;以…...

Mysql—修改用户密码(重置密码)

Mysql—修改用户密码&#xff08;重置密码&#xff09; 1、登录mysql 1 2 [rootlocalhost ~]# mysql -uroot -p123456 [rootlocalhost ~]# mysql -hlocalhost -uroot -p123456 如果忘记密码&#xff0c;则跳过MySQL的密码认证过程。步骤如下&#xff1a; 修改Mysql配置文件…...

ECE585 Tomasulo算法:C++ Tomasulo算法模拟器

ECE585 Tomasulo算法&#xff1a;C Tomasulo算法模拟器 在计算机科学中&#xff0c;Tomasulo算法是一种动态调度和动态执行的方法&#xff0c;它可以有效地处理计算机指令的依赖性。这种算法由IBM的Robert Tomasulo发明&#xff0c;最初用于IBM 360/91的浮点单元。在这篇文章中…...

Qt中在QLabel上画点,重写QLabel类

Qt中在QLabel上画点&#xff0c;重写QLabel类 QT中label进行绘图 1.首先新建一个类&#xff0c;让这个类继承QLabel 2.在类中对鼠标点击事件及绘图事件进行重写 3.然后在UI框架下添加label控件&#xff0c; 4.右键label控件&#xff0c;添加重写的类&#xff0c;将其提升为刚…...

ssm+vue小型企业办公自动化系统源码和论文PPT

ssmvue小型企业办公自动化系统源码和论文PPT013 开发工具&#xff1a;idea 数据库mysql5.7(mysql5.7最佳) 数据库链接工具&#xff1a;navcat,小海豚等 开发技术&#xff1a;java ssm tomcat8.5 摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xf…...

C++ STL priority_queue

目录 一.认识priority_queue 二. priority_queue的使用 三.仿函数 1.什么是仿函数 2.控制大小堆 3.TopK问题 四.模拟实现priority_queue 1.priority_queue的主要接口框架 2.堆的向上调整算法 3.堆的向下调整算法 4.仿函数控制大小堆 五.priority_queue模拟实现整体代码和测…...

[PyTorch][chapter 50][创建自己的数据集 2]

前言&#xff1a; 这里主要针对图像数据进行预处理.定义了一个 class Pokemon(Dataset) 类&#xff0c;实现 图像数据集加载,划分的基本方法. 目录&#xff1a; 整体框架 __init__ load_images save_csv divide_data __len__ denormalize __g…...

SQL-每日一题【1341. 电影评分】

题目 表&#xff1a;Movies 表&#xff1a;Users 请你编写一个解决方案&#xff1a; 查找评论电影数量最多的用户名。如果出现平局&#xff0c;返回字典序较小的用户名。查找在 February 2020 平均评分最高 的电影名称。如果出现平局&#xff0c;返回字典序较小的电影名称。 …...

基于DBN的伪测量配电网状态估计,DBN的详细原理

目录 背影 DBN神经网络的原理 DBN神经网络的定义 受限玻尔兹曼机(RBM) DBN的伪测量配电网状态估计 基本结构 主要参数 数据 MATALB代码 结果图 展望 背影 DBN是一种深度学习神经网络,拥有提取特征,非监督学习的能力,是一种非常好的分类算法,本文将DBN算法伪测量配电网…...

Python运算符全解析:技巧与案例探究

在Python编程中&#xff0c;运算符是强大的工具&#xff0c;能够使我们在数据处理和逻辑判断方面更加灵活。本篇博客将全面探讨Python中常用的运算符&#xff0c;包括算术、比较、逻辑、赋值、位、成员和身份运算符&#xff0c;通过实际案例为你展示如何妙用运算符解决问题。 …...

NPCon:AI模型技术与应用峰会北京站 (参会感受)

8月12日&#xff0c;我有幸参加了在北京皇家格兰云天大酒店举行的“AI模型技术与应用峰会”。 这次会议邀请了很多技术大咖&#xff0c;他们围绕&#xff1a; 六大论点 大模型涌现&#xff0c;如何部署训练架构与算力芯片 LLM 应用技术栈与Agent全景解析 视觉GPU推理服务部署 …...

为什么爬虫要用高匿代理IP?高匿代理IP有什么优点

只要搜代理IP&#xff0c;度娘就能给我们跳出很多品牌的推广&#xff0c;比如我们青果网路的。 正如你所看到的&#xff0c;我们厂商很多宣传用词都会用到高匿这2字。 这是为什么呢&#xff1f;高匿IP有那么重要吗&#xff1f; 这就需要我们从HTTP代理应用最多最广的&#xf…...

【JavaWeb】MySQL约束、事务、多表查询

1 约束 PRIMARY KEY 主键约束 UNIQUE 唯一约束 NOT NULL 非空约束 DEFAULT 默认值约束 FOREIGN KEY 外键约束 主键 主键值必须唯一且非空&#xff1b;每个表必须有一个主键 建表时主键约束 CREATE TABLE 表名 (字段名 字段类型 PRIMARY KEY,字段名 字段类型 );CR…...

【并发编程】自研数据同步工具优化:创建线程池多线程异步去分页调用其他服务接口获取海量数据

文章目录 场景&#xff1a;解决方案 场景&#xff1a; 前段时间在做一个数据同步工具&#xff0c;其中一个服务的任务是调用A服务的接口&#xff0c;将数据库中指定数据请求过来&#xff0c;交给kafka去判断哪些数据是需要新增&#xff0c;哪些数据是需要修改的。 刚开始的设…...

七、dokcer-compose部署springboot的jar

1、准备 打包后包名为 ruoyi-admin.jar 增加接口 httpL//{ip}:{port}/common/test/han #环境变量预application.yml 中REDIS_HOSTt的值&#xff0c;去环境变量去找&#xff1b;如果找不到REDIS_HOST就用myredis 1、Dockerfile FROM hlw/java:8-jreRUN ln -sf /usr/share/z…...

k8s 使用 containerd 运行时配置 http 私服

简介 Kubernetes 从 v1.20 开始弃用 Docker&#xff0c;并推荐用户切换到基于容器运行时接口&#xff08;CRI&#xff09;的容器引擎&#xff0c;如 containerd、cri-o 等。 目前使用的环境中使用了 Kubernetes v1.22.3&#xff0c;containerd 1.4.3&#xff0c;containerd 在…...

【新品发布】ChatWork企业知识库系统源码

系统简介 基于前后端分离架构以及Vue3、uni-app、ThinkPHP6.x、PostgreSQL、pgvector技术栈开发&#xff0c;包含PC端、H5端。 ChatWork支持问答式和文档式知识库&#xff0c;能够导入txt、doc、docx、pdf、md等多种格式文档。 导入数据完成向量化训练后&#xff0c;用户提问…...

疫情打卡 vue+springboot疾病防控管理系统java jsp源代码

本项目为前几天收费帮学妹做的一个项目&#xff0c;Java EE JSP项目&#xff0c;在工作环境中基本使用不到&#xff0c;但是很多学校把这个当作编程入门的项目来做&#xff0c;故分享出本项目供初学者参考。 一、项目描述 疫情打卡 vuespringboot 系统有1权限&#xff1a;管理…...

python --连接websocket

如果只是模拟js端发送接收的话&#xff0c;已经有了websocket server的话&#xff0c;只有client就好了 pip install websocket-client#-*- encoding:utf-8 -*-import sys sys.path.append("..") from socket import * import json, time, threading from websocket…...

数据库内日期类型数据大于小于条件查找注意事项

只传date格式的日期取查datetime的字段的话默认是 00:00:00 日期类型字符串需要使用 ’ ’ 单引号括住 使用大于小于条件查询某一天的日期数据 前后判断条件不能是同一天 一个例子 数据库内数据&#xff1a; 查询2023-08-14之后的数据&#xff1a; select * from tetst…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...