当前位置: 首页 > 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;如果 如果 队伍太长 就加一个激活函数也…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...