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

经典算法判断一个图中是否有环

news 来源：原创 2025/8/26 13:26:51

判断一个图中是否有环

问题描述

给一个以0 0结尾的整数对列表，除0 0外的每两个整数表示一条连接了这两个节点的边。假设节点编号不超过100000大于0。你只要判断由这些节点和边构成的图中是否存在环。存在输出YES，不存在输出NO。

在这里插入图片描述

输入样例1

6 8  5 3  5 2  6 4 5 6  0 0

输出样例1

NO

输入样例2

8 1  7 3  6 2  8 9  7 5 7 4  7 8  7 6  0 0

输出样例2

NO

输入样例3

3 8  6 8  6 4 5 3  5 6  5 2  0 0

输出样例3

YES

输入样例4

1 2 3 4 0 0

输出样例4

NO

输入样例5

空图没有环

0 0

输出样例5

NO

c++代码

#include<bits/stdc++.h>using namespace std;int a, b;
int arr[100001];
bool key = false;int myfind(int x) {int root = x;while(root != arr[root]) root = arr[root];int i = x, j;while(i != root) {j = arr[i];arr[i] = root;i = j;}return root;
}void mymerge(int x, int y) {x = myfind(x), y = myfind(y);if (x != y) arr[y] = arr[x];
}int main() {for (int i = 1; i <= 100000; i++) arr[i] = i;while(true) {scanf("%d %d", &a, &b);if (a == 0 && b == 0) break;if (key) continue;int x = myfind(a), y = myfind(b);if (x == y) key = true;else mymerge(a, b);}if (key) printf("YES");else printf("NO");return 0;
}//by wqs

算法解析

给每个点一个初始的编号，并初始化所有节点的父亲为本身。每新加入一条边就把边相连的两个集合合并到一起，如果边相连的集合原本就是同一个，说明已经成环。

经典算法判断一个图中是否有环

判断一个图中是否有环问题描述给一个以0 0结尾的整数对列表，除0 0外的每两个整数表示一条连接了这两个节点的边。假设节点编号不超过100000大于0。你只要判断由这些节点和边构成的图中是否存在环。存在输出YES，不存在输出NO。输入样例1 6 8 5 3 …...

编程日记 2025/8/26 13:26:51

Transformer-PyTorch实战项目——文本分类

Transformer-PyTorch实战项目——文本分类 ———————————————————————————————————————————— 【前言】这篇文章将带领大家使用Hugging Face里的模型进行微调，并运用在我们自己的新项目——文本分类中。需要大家提前下…...

编程日记 2025/8/20 8:13:34

Linux-服务器负载评估方法

在 Linux 服务器中，top 命令显示的 load average（平均负载）反映了系统在特定时间段内的负载情况。它通常显示为三个数值，分别代表过去 1 分钟、5 分钟和 15 分钟的平均负载。 1. 什么是 Load Average？ Load average …...

编程日记 2025/8/25 20:10:56

Transformer编程题目，结合RTX 3060显卡性能和市场主流技术

以下是10道针对4年经验开发者的Transformer编程题目，结合RTX 3060显卡性能和市场主流技术，每题包含模型选择和实现逻辑描述： 题目1：医疗报告结构化提取模型选择：BioBERT-base 要求： 开发从PDF医疗报告中提…...

编程日记 2025/8/26 22:09:18

Web三漏洞学习（其二：sql注入）

靶场：NSSCTF 、云曦历年考核题二、sql注入 NSSCTF 【SWPUCTF 2021 新生赛】easy_sql 这题虽然之前做过，但为了学习sql，整理一下就再写一次打开以后是杰哥的界面注意到html网页标题的名称是 “参数是wllm” 那就传参数值试一试首先判…...

编程日记 2025/8/26 8:17:43

VLAN的知识

1.什么是VLAN？ VLAN是虚拟局域网，逻辑隔离广播域和网络区域是一种通过将局域网内的设备逻辑地划分为一个个网络的技术 2.对比逻辑网络分割和物理网络分割？ 逻辑网络分割是VLAN，隔离广播域和网络区域物理网络分割是路由&…...

编程日记 2025/8/24 15:10:55

RFID 赋能部队智能物联网仓储建设：打造信息化高效解决方案

在当今军事现代化进程的宏大背景下，部队后勤保障工作无疑占据着举足轻重的地位，而仓储管理作为其中的核心环节，更是至关重要。传统的仓储管理模式在面对当下物资种类繁杂、数量庞大的现状时，已显得力不从心，效率低下、…...

编程日记 2025/8/26 4:06:35

结构型屏蔽在高频电子设备中的应用与优化

在当今高度电子化的时代，随着电子产品工作频率不断提高，设备内部温度上升，电磁环境日趋复杂，电磁兼容（EMC）问题成为设计和制造过程中必须重点解决的问题。EMC不仅关系到设备自身的稳定运行，更涉…...

编程日记 2025/8/26 7:58:31

【教程】Ubuntu修改ulimit -l为unlimited

转载请注明出处：小锋学长生活大爆炸[xfxuezhagn.cn] 如果本文帮助到了你，欢迎[点赞、收藏、关注]哦~ 目录问题描述解决方法一解决方法二解决方法三 (终极) 问题描述查系统资源限制 ulimit -l如果返回的是 64 或其他较小值，那么RDM…...

编程日记 2025/8/23 3:58:41

【HDFS】BlockPlacementPolicyRackFaultTolerant#getMaxNode方法的功能及具体实例

方法参数说明： numOfChosen：已经选择的节点数numOfReplicas：还需要选择的副本数方法的返回值是一个长度为2的数组：[调整后的要选出多少个节点（不包括已经选择的）, 每个机架最大能选择的节点数] @Overrideprotected int[] getMaxNodesPerRack(int numOfChosen, int numOfR…...

编程日记 2025/8/26 10:11:52

水污染治理（生物膜+机器学习）

文章目录 **1. 水质监测与污染预测****2. 植物-微生物群落优化****3. 系统设计与运行调控****4. 维护与风险预警****5. 社区参与与政策模拟****挑战与解决思路****未来趋势** 前言： 将机器学习（ML）等人工智能技术融入植树生物膜系统&#xff…...

编程日记 2025/8/26 11:10:21

数模小白变大神的日记2025.4.15日

分工 1.论文:mathtype (Latex) 2.建模；相应的建模知识与撰写方法，写摘要 3.编程:matlab、SPSs、(Python) 评价模型 1. 层次分析法 ①层次分析法是一种多目标、多准则的决策问题 ②层次分析法是一种主观加权法 ③层次分析法通过以下步骤实现: 1.构…...

编程日记 2025/8/25 14:56:55

STM32提高篇: 以太网通讯

STM32提高篇: 以太网通讯一.以太网通讯介绍二.W5500芯片介绍1.W5500芯片特点2.W5500应用目标3.接入框图三.驱动移植四.tcp通讯五.udp通讯六.http_server 一.以太网通讯介绍以太网（Ethernet）是一种计算机局域网技术。IEEE组织的IEEE 802.3标准制定了以…...

编程日记 2025/8/24 6:16:25

4-15记录（冒泡排序，快速选择排序）

算法稳定简单选择排序的实质就是最后一个和第一个比较，小，就换位置，然后继续用最后一个数字和第二个比较，以此类推。但是算法不稳定，本来下划线的2在后面，但是经过算法后去了前面快速排序实现过程&am…...

编程日记 2025/8/24 13:41:00

Ubuntu系统18.04更新驱动解决方法

原始是：ubuntu18.04里面的驱动是470，对应cuda11.4 现在需要更新为525，对应cuda为12.0 实现： 1、打开终端 Ctrl Alt T2、使用 lspci 命令（快速查看显卡型号） lspci | grep -i vga3、终端输入 ubuntu-d…...

编程日记 2025/8/26 11:07:35

Rocky Linux 9.x 基于 kubeadm部署k8s

搭建集群使用docker下载K8s，使用一主两从模式主机名IP地址k8s- master192.168.1.141k8s- node-1192.168.1.142k8s- node-2192.168.1.143 一：准备工作 VMware Workstation Pro新建三台虚拟机Rocky Linux 9（系统推荐最小化安装） …...

编程日记 2025/8/24 6:43:14

MATLAB程序实现了一个物流配送优化系统，主要功能是通过遗传算法结合四种不同的配送策略，优化快递订单的配送方案

%% 主函数部分 % function main()clear; clc; close all;% 生成或加载算例 filename = D:\快递优化\LogisticsInstance.mat; if ~exist(filename, file)instance = generate_instance();save(filename, -struct, instance); elseinstance = load(filename); end% 遗传算法参数配…...

编程日记 2025/8/26 11:35:28

利用宝塔面板搭建RustDesk服务

一、介绍 1.1官网 https://rustdesk.com/ 1.2github仓库 https://github.com/rustdesk/rustdesk 1.3特点 RustDesk 支持多种操作系统，包括 Windows、macOS、Linux、Android 和 iOS。它甚至提供网页版客户端，可以在浏览器中直接使用。用户可以通过…...

编程日记 2025/8/24 23:16:15

前端与Java后端交互出现跨域问题的14种解决方案

跨域问题是前端与后端分离开发中的常见挑战，以下是14种完整的解决方案： 1 前端解决方案( 开发环境代理) 1.1 Webpack开发服务器代理 // vue.config.js 或 webpack.config.js module.exports {devServer: {proxy: {/api: {target: http://localhost:8…...

编程日记 2025/8/25 9:56:21

PBKDF2全面指南（SpringBoot实现版）

文章目录第一部分：PBKDF2基础概念1. 什么是PBKDF2？2. 为什么需要PBKDF2？3. PBKDF2的工作原理4. PBKDF2与其他密码散列函数的比较第二部分：在Java和SpringBoot中使用PBKDF21. Java内置的PBKDF2支持2. SpringBoot中集成PBKDF22.1 添加依赖2.2 配置PBKDF2密码编码器2.3 自定义…...

编程日记 2025/8/22 21:08:05

基于RV1126开发板的rknn-toolkit-lite使用方法

1. rknn-toolkit-lite介绍 rknn-toolkit-lite是用于python算法的推理的组件，当前已经在EASY-EAI-Nano完成适配，用户可以用它进行深度学习算法的纯python开发。而且同时支持已经进行了预编译的模型，短短几行代码即可完成算法的推理&#xff0c…...

编程日记 2025/8/25 14:14:52

一款轻量级的PHP地址发布页面源码

源码介绍一款轻量级的PHP链接发布页面源码，适合快速搭建个性化的链接导航网站，支持动态链接管理和多种风格模板切换 1：后台登录地址为/admin/login.php，提供便捷的配置入口。 2：默认用户名是admin，密码为…...

编程日记 2025/8/26 7:55:34

分布式计算领域的前沿工具：Ray、Kubeflow与Spark的对比与协同

在当今机器学习和大数据领域，分布式计算已成为解决大规模计算问题的关键技术。本文将深入探讨三种主流分布式计算框架——Ray、Kubeflow和Spark，分析它们各自的特点、应用场景以及如何结合它们的优势创建更强大的计算平台。 Spark批量清洗快，…...

编程日记 2025/8/24 1:13:35

【专题刷题】双指针（一）

📝前言说明： 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分每题主要记录：1，本人解法本人屎山代码；2，优质解法优质代码；3，精益求精，…...

编程日记 2025/8/25 13:05:46

火山引擎旗下防御有哪些

首先，我需要确认用户是不是打错了，比如把“引擎”当成了“云”，或者他们真的想了解火山引擎的防御机制。火山引擎是字节跳动旗下的云服务平台，类似于阿里云或腾讯云，所以用户可能想了解的是其安全防护措施。接下来&am…...

编程日记 2025/8/26 8:54:21

python程序打包——nuitka使用

目前python打包成exe的工具主要有：PyInstaller Briefcase py2exe py2app Nuitka CX_Freeze等。不同于C代码，可以直接编译成可执行的exe文件，或者js代码在浏览器中就能执行，python代码必须通过python解释器来运行&#xff0c…...

编程日记 2025/8/26 1:34:42

编写了一个专门供强化学习玩的贪吃蛇小游戏，可以作为后续学习的playgraound

文章目录 **试玩效果****项目背景****核心设计思路****代码亮点解析****与强化学习算法的对接示例****扩展方向****总结****完整代码**把训练一个会玩小游戏的智能体，作为学习强化学习的一个目标，真的是很有乐趣的一件事。我已经不知为此花费了多少日夜了。如今已是着魔了一般…...

编程日记 2025/8/26 20:45:59

chain_type=“stuff 是什么？其他方式有什么？

chain_type="stuff 是什么？其他方式有什么？目录 chain_type="stuff 是什么？其他方式有什么？1. `chain_type="stuff"`2. `chain_type="map_reduce"`3. `chain_type="refine"`4. `chain_type="map_rerank"`在 LangCh…...

编程日记 2025/8/24 10:01:22

在IDEA里面建立maven项目（便于java web使用）

具体步骤： 第一次有的电脑你再创建项目的时候右下角会提醒你弹窗：让你下载没有的东西一定要下载！！可能会很慢运行结果： 因为他是默认的8080端口所以在运行的时候输入的url如下图： 新建了一个controller代…...

编程日记 2025/8/21 11:16:17

MyBatis 详解

1. 什么是 MyBatis？ MyBatis 是一款优秀的持久层框架，它通过 XML 或注解配置，将 Java 对象（POJO）与数据库操作（SQL）进行灵活映射，简化了 JDBC 的复杂操作。核心思想：S…...

编程日记 2025/8/26 19:31:27

郑州工程技术学院党委书记甘勇一行莅临埃文科技调研交流

为深化产教融合、推动人工智能领域人才培养与产业需求精准对接，2025年4月9日下午，郑州工程技术学院党委书记甘勇、河南省人工智能产业创新发展联盟执行秘书长孟松涛等一行莅临埃文科技调研交流。一、聚焦技术前沿共话AI产业变革座谈会上，…...

编程日记 2025/8/25 19:37:00

AI应用开发之扣子第一课-夸夸机器人

首先，进入官网：点击跳转至扣子。 1.创建智能体登录进网站后，点击左上角＋图标，创建智能体，输入智能体名称、功能介绍 2.输入智能体提示词在“人设与回复逻辑”输入以下内容： # 角色你是一…...

编程日记 2025/8/26 20:15:19

Node.js 数据库 CRUD 项目示例

希望使用Nodejs操作数据库做CRUD，用deepseek实战搜索“使用Nodejs对数据库表做CRUD的项目例子”，找到了解决方案，如下图所示： 项目结构 nodejs-crud-example/ ├── config/ │ └── db.js # 数据库连接配置 ├──…...

编程日记 2025/8/26 8:06:57

ESP8266/32作为AVR编程器(ISP programmer)的使用介绍

ESP8266作为AVR编程器( ISP programmer)的使用介绍 🌿ESP8266自带库例程：https://github.com/esp8266/Arduino/tree/master/libraries/ESP8266AVRISP📍支持ESP8266/32的ESP_AVRISP其它开源工程（个人没有再去验证）&…...

编程日记 2025/8/26 18:11:55

union all几个常见问题及其解决方案

UNION ALL 是 SQL 中用于合并两个或多个 SELECT 语句结果集的操作符。与 UNION 不同，UNION ALL 不会去除重复的记录，它简单地将一个查询的结果附加到另一个查询的结果之后。尽管 UNION ALL 相对来说更高效（因为它不需要检查重复项&#xff09…...

编程日记 2025/8/20 9:16:33

21.C++11

1.列表初始化 1.1C11中的{} •C11以后想统⼀初始化⽅式，试图实现⼀切对象皆可⽤{}初始化，{}初始化也叫做列表初始化。 • 内置类型⽀持，⾃定义类型也⽀持，⾃定义类型本质是类型转换，中间会产⽣临时对象，最…...

编程日记 2025/8/25 8:37:55

【交叉编译】目标机编译安装对应依赖库总结

1、解压目标机交叉编译工具链 # 创建工具链存放目录（可选） sudo mkdir -p /opt/toolchain# 解压到目标路径（示例路径：/opt/toolchain） sudo tar -xzvf 目标主机编译工具链.tar.gz -C /opt/toolchain# 查看解压后的目录…...

编程日记 2025/8/26 0:12:03

Docker华为云创建私人镜像仓库

Docker华为云创建私人镜像仓库在华为云官网的产品中搜索容器镜像服务 ： 或者在其他页面的搜索栏中搜索容器镜像服务 ： 进入到页面后，点击创建组织 （华为云的镜像仓库称为组织）： 设置组织名字后&…...

编程日记 2025/8/25 18:45:04

【15】数据结构之基于树的查找算法篇章

目录标题二叉排序树 Binary Sort Tree二叉排序树的插入二叉树排序树的删除二叉排序树的查找二叉排序树的调试与代码集合平衡二叉树-AV树平衡二叉树的平衡化旋转平衡二叉树的代码调试与代码集合 B树Ｂ树的查找B树的插入B树和B*树二叉排序树 Binary Sort Tree 二叉…...

编程日记 2025/8/26 7:58:26

自定义类型之结构体

1.结构体类型概述结构体类型是一种用户自定义的数据类型，用于将不同类型的数据组合成一个整体。在C语言中，结构体使用struct关键字定义，由一系列具有相同类型或不同类型的数据构成的数据集合，也称为结构。结构体中的数据在逻辑上…...

编程日记 2025/8/26 18:26:59

SGFormer：卫星-地面融合 3D 语义场景补全

论文介绍题目：SGFormer: Satellite-Ground Fusion for 3D Semantic Scene Completion 会议：IEEE / CVF Computer Vision and Pattern Recognition Conference 论文：https://www.arxiv.org/abs/2503.16825 代码：https://githu…...

编程日记 2025/8/25 8:47:33

应急响应篇钓鱼攻击邮件与文件EML还原蠕虫分析线索定性处置封锁

钓鱼邮件的eml中会有邮件服务器地址域名（发信人）发送的本地IP和主机名发送的内容以及附件邮件钓鱼： 攻击者目的：通过发信人，附件，取得突破定性钓鱼邮件威胁情报，人工分析来源&#xff0c…...

编程日记 2025/8/20 20:43:50

利用纯JS开发浏览器小窗口移动广告小功能

效果展示直接上代码如果要用到vue项目里面，直接按照vue的写法改动就行，一般没有多大的问题，顶部的占位是我项目需求，你可以按照要求改动。 <!DOCTYPE html> <html> <head><meta charset"utf-8"…...

编程日记 2025/8/25 17:14:52

java Stream流

Stream流双列集合无法直接使用stream流，可以通过keyset（）或enteyset转换为单列集合，再进行操作 1.单列集合 package mystream;import java.util.ArrayList; import java.util.Collections;public class StreamDemo1 {public sta…...

编程日记 2025/8/26 21:38:25

【实战中提升自己】防火墙篇之VPX部署–L2TP over IPSEC

1 VPx部署【L2TP Over ipsec】说明：在VPX上面，我们希望与分部建立VPX，保证与分部的财务部正常通信，另外还提供L2TP Over ISPEC功能，方便远程接入访问内部服务器等。当然我们也可以做详细的控制&#xff…...

编程日记 2025/8/26 16:54:54

贪心算法（20）（java）整数替换

给定一个正整数 n ，你可以做如下操作： 如果 n 是偶数，则用 n / 2替换 n 。如果 n 是奇数，则可以用 n 1或n - 1替换 n 。返回 n 变为 1 所需的最小替换次数。示例 1： 输入：n 8 输出：3 解…...

编程日记 2025/8/26 7:20:08

实验二．单按键控制LED

1．实验任务如图4.1所示：在P0.0端口上接一个发光二极管L1，按键按一下灯亮，在按一下灯灭。 2．电路原理图 3．系统板上硬件连线把“单片机系统”区域中的P0端口用导线连接到“八路发光二极管指示模块”区域中的L1端口上。 4．程序设计内容...

编程日记 2025/8/26 17:28:24

Ubuntu 常用命令行指令

1. 文件与目录操作命令作用示例ls列出目录内容ls -l（详细列表）cd切换目录cd ~/Documentspwd显示当前目录路径pwdmkdir创建目录mkdir new_folderrm删除文件rm file.txtrm -r递归删除目录rm -r old_dircp复制文件cp file.txt backup/mv移动/重命名文件mv…...

编程日记 2025/8/26 13:55:21

Cribl 数据脱敏 -02 (附测试数据）

先把实验的测试方向如下: Match Regex Replace Expression Example result <...

编程日记 2025/8/25 22:22:15

【项目管理】第16章项目采购管理-- 知识点整理

项目管理-相关文档，希望互相学习，共同进步风123456789～-CSDN博客 （一）知识总览项目管理知识域知识点： （项目管理概论、立项管理、十大知识域、配置与变更管理、绩效域） 对应&…...

编程日记 2025/8/26 16:18:23

判断一个图中是否有环

问题描述

算法解析

相关文章：