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

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

图:
在这里插入图片描述

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

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);}}
}

结果:
在这里插入图片描述

相关文章:

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

图&#xff1a; 有向图查询所有环&#xff0c;非递归&#xff1a; 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功能

实现步骤&#xff1a; 1.导入WebSocket坐标。 在pom.xml中增加依赖项&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dependency>2.编写WebSocket配…...

HTML5的新特性

目录 一&#xff0c;新增语义化标签 二&#xff0c;新增的多媒体标签 三&#xff0c;新增input表单 四&#xff0c;新增的表单属性 一&#xff0c;新增语义化标签 二&#xff0c;新增的多媒体标签 1&#xff0c;音频&#xff1a;<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 …...

关于修改数据库服务器时间导致达梦数据库集群裂开

故障原因&#xff1a; 因为每天数据库服务器时间都不一致&#xff0c;想要给数据库服务器配置个NTP服务器。结果导致达梦数据库裂库。后面查看了达梦系统管理员手册了解了达梦集群的机制&#xff0c;知道数据库服务器时间需要先关闭数据库服务之后才可以修改数据库服务器时间。…...

自定义包的设计与实现

这是一个 CPacket 类&#xff0c;用于解析包含固定格式的数据。该类的成员变量包括固定包头 sHead、包长度 nLength、控制命令 sCmd、包数据 strData 和和校验 sSum。 构造函数&#xff1a; CPacket()&#xff1a;默认构造函数&#xff0c;初始化成员变量。 CPacket(const B…...

时机成熟了

时机成熟了。 有一个老乡群&#xff0c;一到年底就各种人找车、车找人的消息。这些消息如果能直接爬取到一个小的网页里面去&#xff0c;则可以极大地便利大家做检索。如何把非结构化的内容转成结构化的 json&#xff0c;在以前是一个难题&#xff0c;但是有了 ChatGPT&#x…...

Linux 驱动开发基础知识——总线设备驱动模型(八)

个人名片&#xff1a; &#x1f981;作者简介&#xff1a;学生 &#x1f42f;个人主页&#xff1a;妄北y &#x1f427;个人QQ&#xff1a;2061314755 &#x1f43b;个人邮箱&#xff1a;2061314755qq.com &#x1f989;个人WeChat&#xff1a;Vir2021GKBS &#x1f43c;本文由…...

SpringBoot+BCrypt算法加密

BCrypt是一种密码哈希函数&#xff0c;BCrypt算法使用“盐”来加密密码&#xff0c;这是一种随机生成的字符串&#xff0c;可以在密码加密过程中使用&#xff0c;以确保每次加密结果都不同。盐的使用增强了安全性&#xff0c;因为攻击者需要花费更多的时间来破解密码。 下图为…...

更新至2023年,2002-2023年3月中国国债发行数据

更新至2023年&#xff0c;2002-2023年3月中国国债发行数据 1、时间&#xff1a;2002-2023年3月 2、指标&#xff1a;序号、代码、发行日期、发行总额(亿元)、期限(年)、发行价格、票面利率(发行参考利率)(%)、票面利率说明、息票品种、附息利率类型、付息频率、起息日期、付息…...

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 的一个超集&#xff0c;…...

国外知名的农业机器人公司

从高科技温室到云播种&#xff0c;农业机器人如何帮助农民填补劳动力短缺以及超市货架的短缺。 概要 “高科技农业”并不矛盾。当代农业经营更像是硅谷&#xff0c;而不是美国哥特式&#xff0c;拥有控制灌溉的应用程序、驾驶拖拉机的 GPS 系统和监控牲畜的带有 RFID 芯片的耳…...

【EI会议征稿中|ACM出版】#先投稿,先送审#第三届网络安全、人工智能与数字经济国际学术会议(CSAIDE 2024)​

#先投稿&#xff0c;先送审#ACM出版#第三届网络安全、人工智能与数字经济国际学术会议&#xff08;CSAIDE 2024&#xff09; 2024 3rd International Conference on Cyber Security, Artificial Intelligence and Digital Economy 2024年3月8日-10日 | 中国济南 会议官网&…...

【笔试常见易错选择题01】else、表达式、二维数组、%m.ns、%m.nf、常量指针和指针常量、宏定义、传参、数组越界、位段

1. 下列main()函数执行后的结果为&#xff08;&#xff09; 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 判断为赋值语句&#xff0c;j等于0 0为假不进循环 选B. 2. 下面程…...

Unity中常见的单词

前言 unity中常见的单词学习积累 一.常用的基础词。 new:新建; as:像。。一样; null:对象空值; void:函数返回空值; switch:开关; abstract:抽象的; event:事件&#xff1b; return:返回; class:类; …...

【仅需一步,1分钟极速开服】幻兽帕鲁保姆级教程

本教程分为两部分。一、开服教程。二、如何登录游戏&#xff08;第一次接触游戏&#xff0c;如何玩&#xff09; 一、开服教程。 1、通过 游戏服务器专属优惠页&#xff0c;选择以下应用模板并点击立即购买。 - 【服务器套餐配置推荐】* 1、入门配置&#xff08;2&#xff5e;…...

Zoho Mail 2023:回顾过去,展望未来:不断进化的企业级邮箱解决方案

当我们告别又一个非凡的一年时&#xff0c;我们想回顾一下Zoho Mail如何融合传统与创新。我们迎来了成立15周年&#xff0c;这是一个由客户、合作伙伴和我们的敬业团队共同庆祝的里程碑。与我们一起回顾这段旅程&#xff0c;探索定义Zoho Mail历史篇章的敏捷性、精确性和创新性…...

python执行linux系统命令的三种方式

前言 这是我在这个网站整理的笔记,有错误的地方请指出&#xff0c;关注我&#xff0c;接下来还会持续更新。 作者&#xff1a;神的孩子都在歌唱 1. 使用os.system 无法获取命令执行后的返回信息 import osos.system(ls)2. 使用os.popen 能够获取命令执行后的返回信息 impor…...

协会认证!百望云荣获信创工委会年度“卓越贡献成员单位”称号

当前&#xff0c;新一轮科技革命和产业变革正加速重塑全球经济结构&#xff0c;强化企业科技创新的主体地位&#xff0c;推动创新链、产业链、人才链深度融合&#xff0c;加快科技成果产业化进程至关重要。 近日&#xff0c;中国电子工业标准化技术协会信息技术应用创新工作委员…...

神经网络激活函数到底是什么?

激活函数 其实不是很难啦&#xff0c;归结一下就是大概这样几个分类&#xff0c;详情请参考【神经网络】大白话直观理解&#xff01;_哔哩哔哩_bilibili神经网络就是干这个事的~ 如果队伍不长&#xff0c;一个ykxb就可以了&#xff0c;如果 如果 队伍太长 就加一个激活函数也…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...