有向图查询所有环,非递归
图:

有向图查询所有环,非递归:
import java.util.*;public class CycleTest {private final int V; // 顶点数private final List<List<Integer>> adjList; // 邻接表public CycleTest(int vertices) {this.V = vertices;this.adjList = new ArrayList<>(vertices);for (int i = 0; i < vertices; i++) {adjList.add(new LinkedList<>());}}// 添加有向边public void addEdge(int src, int dest) {adjList.get(src).add(dest);}// 查找所有环public List<List<Integer>> findAllCycles() {List<List<Integer>> cycles = new ArrayList<>();Stack<Integer> stack = new Stack<>();Stack<Integer> pathStack = new Stack<>();Stack<Integer> neighborPoint = new Stack<>();Stack<Integer> levelStack = new Stack<>();boolean[] visited = new boolean[V];int level = 1;for (int startVertex = 0; startVertex < V; startVertex++) {if (visited[startVertex]) {continue;}stack.push(startVertex);pathStack.push(startVertex);while (!stack.isEmpty() || !neighborPoint.isEmpty()) {if (stack.isEmpty()) {int l = levelStack.pop();// 返回上一个邻接点搜索Integer p = neighborPoint.pop();stack.push(p);while (pathStack.size() >= l) {pathStack.pop();}pathStack.push(p);level--;}int vertex = stack.pop();List<Integer> neighbors = adjList.get(vertex);for (int i = 0; i < neighbors.size(); i++) {Integer neighbor = neighbors.get(i);if (i == 0) {if (!pathStack.contains(neighbor)) {stack.push(neighbor);pathStack.push(neighbor);} else {// 找到环List<Integer> cycle = new ArrayList<>();List<Integer> path = pathStack.stream().toList();for(int j = path.size() - 1; j >= 0; j--) {Integer p = path.get(j);cycle.add(p);visited[p] = true;if (Objects.equals(p, neighbor)) {break;}}Collections.reverse(cycle);cycles.add(cycle);}level++;} else {// 存储邻接点neighborPoint.push(neighbor);levelStack.push(level);}}}// 清除路径栈状态pathStack.clear();levelStack.clear();level = 1;}return cycles;}public static void main(String[] args) {CycleTest graph = new CycleTest(4);graph.addEdge(0, 1);graph.addEdge(1, 2);graph.addEdge(2, 0);graph.addEdge(1, 3);graph.addEdge(3, 2);List<List<Integer>> cycles = graph.findAllCycles();System.out.println("Cycles in the directed graph:");for (List<Integer> cycle : cycles) {System.out.println(cycle);}}
}
结果:

相关文章:
有向图查询所有环,非递归
图: 有向图查询所有环,非递归: import java.util.*;public class CycleTest {private final int V; // 顶点数private final List<List<Integer>> adjList; // 邻接表public CycleTest(int vertices) {this.V vertices;this.…...
SpringBoot 使用WebSocket功能
实现步骤: 1.导入WebSocket坐标。 在pom.xml中增加依赖项: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dependency>2.编写WebSocket配…...
HTML5的新特性
目录 一,新增语义化标签 二,新增的多媒体标签 三,新增input表单 四,新增的表单属性 一,新增语义化标签 二,新增的多媒体标签 1,音频:<audio>.。。用MP3 <audio src…...
Filter过滤器学习使用
验证token 对外API过滤器 public class APIFilter implements Filter {private static Logger logger LogManager.getLogger(APIFilter.class);private ICachedTokenService tokenService;public APIFilter(ICachedTokenService tokenService) {super();this.tokenService …...
关于修改数据库服务器时间导致达梦数据库集群裂开
故障原因: 因为每天数据库服务器时间都不一致,想要给数据库服务器配置个NTP服务器。结果导致达梦数据库裂库。后面查看了达梦系统管理员手册了解了达梦集群的机制,知道数据库服务器时间需要先关闭数据库服务之后才可以修改数据库服务器时间。…...
自定义包的设计与实现
这是一个 CPacket 类,用于解析包含固定格式的数据。该类的成员变量包括固定包头 sHead、包长度 nLength、控制命令 sCmd、包数据 strData 和和校验 sSum。 构造函数: CPacket():默认构造函数,初始化成员变量。 CPacket(const B…...
时机成熟了
时机成熟了。 有一个老乡群,一到年底就各种人找车、车找人的消息。这些消息如果能直接爬取到一个小的网页里面去,则可以极大地便利大家做检索。如何把非结构化的内容转成结构化的 json,在以前是一个难题,但是有了 ChatGPT&#x…...
Linux 驱动开发基础知识——总线设备驱动模型(八)
个人名片: 🦁作者简介:学生 🐯个人主页:妄北y 🐧个人QQ:2061314755 🐻个人邮箱:2061314755qq.com 🦉个人WeChat:Vir2021GKBS 🐼本文由…...
SpringBoot+BCrypt算法加密
BCrypt是一种密码哈希函数,BCrypt算法使用“盐”来加密密码,这是一种随机生成的字符串,可以在密码加密过程中使用,以确保每次加密结果都不同。盐的使用增强了安全性,因为攻击者需要花费更多的时间来破解密码。 下图为…...
更新至2023年,2002-2023年3月中国国债发行数据
更新至2023年,2002-2023年3月中国国债发行数据 1、时间:2002-2023年3月 2、指标:序号、代码、发行日期、发行总额(亿元)、期限(年)、发行价格、票面利率(发行参考利率)(%)、票面利率说明、息票品种、附息利率类型、付息频率、起息日期、付息…...
2024最新版TypeScript安装使用指南
2024最新版TypeScript安装使用指南 Installation and Development Guide to the Latest TypeScript in 2024 By JacksonML 1. 什么是TypeScript? TypeScript is JavaScript with syntax for types. – typescriptlang.org TypeScript 是 JavaScript 的一个超集,…...
国外知名的农业机器人公司
从高科技温室到云播种,农业机器人如何帮助农民填补劳动力短缺以及超市货架的短缺。 概要 “高科技农业”并不矛盾。当代农业经营更像是硅谷,而不是美国哥特式,拥有控制灌溉的应用程序、驾驶拖拉机的 GPS 系统和监控牲畜的带有 RFID 芯片的耳…...
【EI会议征稿中|ACM出版】#先投稿,先送审#第三届网络安全、人工智能与数字经济国际学术会议(CSAIDE 2024)
#先投稿,先送审#ACM出版#第三届网络安全、人工智能与数字经济国际学术会议(CSAIDE 2024) 2024 3rd International Conference on Cyber Security, Artificial Intelligence and Digital Economy 2024年3月8日-10日 | 中国济南 会议官网&…...
【笔试常见易错选择题01】else、表达式、二维数组、%m.ns、%m.nf、常量指针和指针常量、宏定义、传参、数组越界、位段
1. 下列main()函数执行后的结果为() int func(){ int i, j, k 0; for(i 0, j -1;j 0;i, j){ k; } return k; } int main(){cout << (func());return 0; }A. -1 B. 0 C. 1 D. 2 判断为赋值语句,j等于0 0为假不进循环 选B. 2. 下面程…...
Unity中常见的单词
前言 unity中常见的单词学习积累 一.常用的基础词。 new:新建; as:像。。一样; null:对象空值; void:函数返回空值; switch:开关; abstract:抽象的; event:事件; return:返回; class:类; …...
【仅需一步,1分钟极速开服】幻兽帕鲁保姆级教程
本教程分为两部分。一、开服教程。二、如何登录游戏(第一次接触游戏,如何玩) 一、开服教程。 1、通过 游戏服务器专属优惠页,选择以下应用模板并点击立即购买。 - 【服务器套餐配置推荐】* 1、入门配置(2~…...
Zoho Mail 2023:回顾过去,展望未来:不断进化的企业级邮箱解决方案
当我们告别又一个非凡的一年时,我们想回顾一下Zoho Mail如何融合传统与创新。我们迎来了成立15周年,这是一个由客户、合作伙伴和我们的敬业团队共同庆祝的里程碑。与我们一起回顾这段旅程,探索定义Zoho Mail历史篇章的敏捷性、精确性和创新性…...
python执行linux系统命令的三种方式
前言 这是我在这个网站整理的笔记,有错误的地方请指出,关注我,接下来还会持续更新。 作者:神的孩子都在歌唱 1. 使用os.system 无法获取命令执行后的返回信息 import osos.system(ls)2. 使用os.popen 能够获取命令执行后的返回信息 impor…...
协会认证!百望云荣获信创工委会年度“卓越贡献成员单位”称号
当前,新一轮科技革命和产业变革正加速重塑全球经济结构,强化企业科技创新的主体地位,推动创新链、产业链、人才链深度融合,加快科技成果产业化进程至关重要。 近日,中国电子工业标准化技术协会信息技术应用创新工作委员…...
神经网络激活函数到底是什么?
激活函数 其实不是很难啦,归结一下就是大概这样几个分类,详情请参考【神经网络】大白话直观理解!_哔哩哔哩_bilibili神经网络就是干这个事的~ 如果队伍不长,一个ykxb就可以了,如果 如果 队伍太长 就加一个激活函数也…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
