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

有向图查询所有环,非递归:
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就可以了,如果 如果 队伍太长 就加一个激活函数也…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...
