有向图的完全可达性(有向图搜索全路径的问题) C#DFs
在考察输入输出方面我觉得是道难题了 第一次遇见邻接表的数据结构该怎么声明
卡码网105 在力扣没找见完全相同的题 感觉需要多练习多复习这种类型的题
105. 有向图的完全可达性
题目描述
给定一个有向图,包含 N 个节点,节点编号分别为 1,2,...,N。现从 1 号节点开始,如果可以从 1 号节点的边可以到达任何节点,则输出 1,否则输出 -1。
输入描述
第一行包含两个正整数,表示节点数量 N 和边的数量 K。 后续 K 行,每行两个正整数 s 和 t,表示从 s 节点有一条边单向连接到 t 节点。
输出描述
如果可以从 1 号节点的边可以到达任何节点,则输出 1,否则输出 -1。
输入示例
4 4
1 2
2 1
1 3
2 4
输出示例
1
提示信息

从 1 号节点可以到达任意节点,输出 1。
数据范围:
1 <= N <= 100;
1 <= K <= 2000。
思路: 深搜 1.确认递归函数 参数
需要传入地图,需要知道当前我们拿到的key,以至于去下一个房间(节点)。
同时还需要一个数组,用来记录我们都走过了哪些房间,
这样好知道最后有没有把所有房间都遍历的,可以定义一个一维数组。
Dfs时的终止条件判断 :如果我们是处理当前访问的节点,当前访问的节点如果是 true ,
说明是访问过的节点,那就终止本层递归,如果不是true,我们就把它赋值为true,
因为这是我们处理本层递归的节点。
需要注意的点:1. List<List<int>> graph=new List<List<int>>(n+1); 数据结构
List<List<int>> 是一个嵌套的 List 类型,表示一个包含多个整数列表的列表。可以把它看作是一个列表的列表。
graph是一个List<List<int>>类型的变量,表示图的邻接表。它包含n + 1个List<int>元素,代表图中的n + 1个节点。- 每个
List<int>用来存储该节点的邻接节点。通过graph[i].Add(x)的方式,将节点i与其他节点x连接起来。 - 使用
string.Join(", ", graph[i])将每个列表中的元素格式化成字符串并打印出来,展示图的邻接关系。


2.List<int> suroudkey= graph[key]; 这一部分的意思是检测到的key节点的相连接的节点取出来 为suroudkey列表中的数 其中的数就是相邻的节点
graph是一个 邻接表,即List<List<int>>类型的数据结构,其中graph[key]代表节点key的所有邻接节点(即节点key直接相连的节点列表)。- suroudkey是一个
List<int>,保存了key节点的所有邻接节点的列表。
- 访问当前节点:在调用
Dfs函数时,当前节点会被访问。通常,DFS 会通过一个visited数组(或集合)来记录哪些节点已经被访问过,以避免重复访问。 - 遍历邻接节点:在
graph[key]中,找出当前节点key所有直接相连的邻接节点,即keys。对每一个邻接节点nextKey,递归地调用Dfs函数进行深度优先遍历。 - 递归过程:递归调用会继续深入到下一个未被访问的邻接节点,直到遍历完当前节点的所有邻接节点。然后回溯到上一个节点,继续访问下一个未被访问的邻接节点。

代码实现:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
//输入模式
string[] input= Console.ReadLine().Split();
int n=int.Parse(input[0]);
int k=int.Parse(input[1]);
//难点:需要进行邻接表初始化
//这个数据结构放到开头解释
List<List<int>> graph=new List<List<int>>(n+1);
for(int i=0;i<=n;i++)
{
graph.Add(new List<int>());
}
//输入除第一行之外的信息 (边的信息)
for(int i=0;i<k;i++)
{
string[] edge=Console.ReadLine().Split();
s=int.Parse(edge[0]);
t=int.Parse(edge[1]);
//使用邻接表 表示s-》t是相连的
graph[s].Add(t);
}
//访问标记数值 这就是我们说的用来记录录都走过了哪些房间的一维数组
bool[] visted=new bool[n+1];
// 从节点一开始进行Dfs遍历
Dfs(graph,1,visted);
//检测是否所有节点都被访问到了
for(int i=1;i<=n;i++)
{
if(visted[i]==false) //如果检测了一遍发现有false 证明有的节点没被访问
{
//输出-1
Console.WriteLine(-1);
return ;
}
//如果检测到的全部都为true 证明全被访问了 输出1
Console.WriteLine(1);
}
}
public static void Dfs( List<List<int>> graph,int key,bool[] visted)
{
//处理当前访问节点
if(visted[key]==true)
{
return ;
}
//因为默认数组中都是false 所以访问一个变一个
visted [key]=true;
List<int> suroudkey=graph[key];//找出当前key的所有相连节点
//开始遍历相连的key 因为是一个列表 都存着数 就直接遍历就行
foreach(int nextkey in suroudkey )
{
Dfs(graph,nextkey,visted);
}
}
}
相关文章:
有向图的完全可达性(有向图搜索全路径的问题) C#DFs
在考察输入输出方面我觉得是道难题了 第一次遇见邻接表的数据结构该怎么声明 卡码网105 在力扣没找见完全相同的题 感觉需要多练习多复习这种类型的题 105. 有向图的完全可达性 题目描述 给定一个有向图,包含 N 个节点,节点编号分别为 1&…...
前端开发实现自定义勾选/自定义样式,可复选,可取消勾选
基于后端返回数组实现多选、复选 以下代码基于vue2,如果有需要React/Vue3或者其他框架代码的,可以通过国内直连GPT4o进行代码转换,转换正确率99% 前端代码如下(直接拷贝到你的vue代码即可): <!-- CustomCheckboxList.vue --&g…...
鸿蒙-promptAction.showToast基于PC屏幕底部提示
PC端app缩小,右击出菜单后,点菜单项 菜单关闭,并弹promptAction.showToast提示,但提示是基于PC底部弹提示的,需要的是基于app底部弹提示 原因是UIContext是右击菜单的UIContext,需要拿到菜单下面UI的UICont…...
Vert.x,应用监控 - 全链路跟踪,基于Zipkin
关于Zipkin Zipkin是一款开源的分布式实时数据追踪系统(Distributed Tracking System),能够收集服务间调用的时序数据,提供调用链路的追踪。Zipkin每一个调用链路通过一个trace id来串联起来,通过trace id,就能够直接定位到这次调…...
Rust常用数据结构教程 序列
文章目录 一、Vec1.Vec与堆栈2.什么时候需要Vec3.get()方法4.与枚举的结合 二、VecDeque1.什么情况适合VecDeque2.VecDeque的方法 三、LinkedList1.什么时候用LinkedList 参考 一、Vec 可变数组(vector)数组存储在heap上,在运行时(runtime)可以增加或减少数组 长度 有人把Ve…...
智慧城市路面垃圾识别系统产品介绍方案
方案介绍 智慧城市中的路面垃圾识别算法通常基于深度学习框架,这些算法因其在速度和精度上的优势而被广泛采用。这些模型能够通过训练识别多种类型的垃圾,包括塑料袋、纸屑、玻璃瓶等。系统通过训练深度学习模型,使其能够识别并定位多种类型…...
网络安全:构建坚固的数字堡垒
网络安全:构建坚固的数字堡垒 在当今数字化时代,网络安全已经成为企业和个人不可忽视的重要议题。随着互联网的普及和信息技术的快速发展,网络攻击、数据泄露和隐私侵犯等问题日益严重,给企业和个人带来了巨大的风险和损失。本文…...
LeetCode题练习与总结:打乱数组--384
一、题目描述 给你一个整数数组 nums ,设计算法来打乱一个没有重复元素的数组。打乱后,数组的所有排列应该是 等可能 的。 实现 Solution class: Solution(int[] nums) 使用整数数组 nums 初始化对象int[] reset() 重设数组到它的初始状态并返回int[]…...
科技改变生活:最新智能开关、调光器及插座产品亮相
根据QYResearch调研团队的最新力作《欧洲开关、调光器和插座市场报告2023-2029》显示,预计到2029年,欧洲开关、调光器和插座市场的规模将攀升至57.8亿美元,并且在接下来的几年里,将以4.2%的复合年增长率(CAGRÿ…...
传统RAG流程;密集检索器,稀疏检索器:中文的M3E
目录 传统RAG流程 相似性搜索中:神经网络的密集检索器,稀疏检索器 密集检索器 BGE系列模型 text-embedding-ada-002模型 M3E模型 稀疏检索器 示例一:基于TF-IDF的稀疏检索器 示例二:基于BM25的稀疏检索器 稀疏检索器的特点与优势 传统RAG流程 相似性搜索中:神经…...
基于统计方法的语言模型
基于统计方法的语言模型 基于统计方法的语言模型主要是指利用统计学原理和方法来构建的语言模型,这类模型通过分析和学习大量语料库中的语言数据,来预测词、短语或句子出现的概率。 N-gram模型:这是最基础的统计语言模型之一,它基…...
Flux comfyui 部署笔记,整合包下载
目录 comfyui启动: 1、下载 Flux 模型 2、Flux 库位置 工作流示例: Flux学习资料免费分享 comfyui启动: # 配置下载模型走镜像站 export HF_ENDPOINT="https://hf-mirror.com" python3 main.py --listen 0.0.0.0 --port 8188 vscode 点击 port 映射到本地,…...
高性能分布式缓存Redis-数据管理与性能提升之道
一、持久化原理 Redis是内存数据库,数据都是存储在内存中,为了避免进程退出导致数据的永久丢失,需要定期将Redis中的数据以某种形式(数据或命令)从内存保存到硬盘;当下次Redis重启时,利用持久化文件实现数据恢复。除此…...
BO-CNN-LSTM回归预测 | MATLAB实现BO-CNN-LSTM贝叶斯优化卷积神经网络-长短期记忆网络多输入单输出回归预测
BO-CNN-LSTM回归预测 | MATLAB实现BO-CNN-LSTM贝叶斯优化卷积神经网络-长短期记忆网络多输入单输出回归预测 目录 BO-CNN-LSTM回归预测 | MATLAB实现BO-CNN-LSTM贝叶斯优化卷积神经网络-长短期记忆网络多输入单输出回归预测效果一览基本介绍模型搭建程序设计参考资料 效果一览 …...
DataWind将字符串数组拆出多行的方法
摘要: 可视化建模中先将字符串split为array再用explode(array)即可 可视化建模 进入“可视化建模”页面 1.1 新建任务 如果团队内没有可视化建模任务。请点击“新建任务”,输入名称并确定。 1.2 建立数据连接 在左边栏中选择“数据连接”,…...
try...catch 和then...catch的异同点分析
try…catch 和 then…catch 的异同点分析 在现代 JavaScript 编程中,异常处理和 Promise 的处理是非常常见的两种方式。try...catch 语句主要用于同步代码的异常处理,而 .then().catch() 是 Promise 中的异步处理方法。 1. 基础概念 1.1 try…catch …...
Mit6.S081-实验环境搭建
Mit6.S081-实验环境搭建 注:大家每次做一些操作的时候觉得不太保险就先把虚拟机克隆一份 前言 qemu(quick emulator):这是一个模拟硬件环境的软件,利用它可以运行我们编译好的操作系统。 准备一个Linux系统…...
以太网交换安全:MAC地址漂移
一、什么是MAC地址漂移? MAC地址漂移是指设备上一个VLAN内有两个端口学习到同一个MAC地址,后学习到的MAC地址表项覆盖原MAC地址表项的现象。 MAC地址漂移的定义与现象 基本定义:MAC地址漂移发生在一个VLAN内的两个不同端口学习到相同的MAC地…...
STM32实现串口接收不定长数据
原理 STM32实现串口接收不定长数据,主要靠的就是串口空闲(idle)中断,此中断的触发条件与接收的字节数无关,只有当Rx引脚无后续数据进入时(串口空闲时),认为这时候代表一个数据包接收完成了&…...
AAA 数据库事务隔离级别及死锁
目录 一、事务的四大特性(ACID) 1. 原子性(atomicity): 2. 一致性(consistency): 3. 隔离性(isolation): 4. 持久性(durability): 二、死锁的产生及解决方法 三、事务的四种隔离级别 0 .封锁协议 …...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
