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

经典算法判断一个图是不是树

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

判断一个图是不是树

问题描述

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

在这里插入图片描述

输入样例1

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

输出样例1

YES

输入样例2

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

输出样例2

YES

输入样例3

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

输出样例3

NO

输入样例4

1 2 3 4 0 0

输出样例4

NO

输入样例5

空树也是树

0 0

输出样例5

YES

c++代码

#include<bits/stdc++.h>
#include<stdio.h>using namespace std;int a, b, cont = 0;
int arr[100001];
bool key = true;
unordered_set<int> st;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) {if (cont == 0) {printf("YES\n");return 0;}if (key && st.size() != cont + 1) key = false;if (key) {int root = -1;for (int x : st) {int k = myfind(x);if (root == -1) root = k;if (k != root) {key = false;break;}}}if (key) printf("YES\n");else printf("NO\n");break;}else {cont++;if (st.find(a) == st.end()) st.insert(a);if (st.find(b) == st.end()) st.insert(b);if (key) {int x = myfind(a), y = myfind(b);if (x == y) key = false;else mymerge(a, b);}}}return 0;
}

算法解析

满足下面三个条件的图是树

1、不存在环。

2、所有点都是互相连通的。

3、点数=边数 + 1。

判断环

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

int x = myfind(a), y = myfind(b);
if (x == y) key = false; //边相连的集合原本就是同一个，说明已经成环，不是生成树。
else mymerge(a, b); //否则合并一下

判断节点数和边数的关系

把点存在一个unordered_set里面就行，因为不能存重复的，边用一个cont就可以存

cont++;
if (st.find(a) == st.end()) st.insert(a);
if (st.find(b) == st.end()) st.insert(b);
......
if (key && st.size() != cont + 1) key = false;

判断连通性

如果是连通的，根据我们之前的合并操作，每一个节点应该都属于同一个集合，如果不是，则不是树。

int root = -1;
for (int x : st) {int k = myfind(x);if (root == -1) root = k;if (k != root) {key = false;break;}
}

经典算法判断一个图是不是树

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

编程日记 2025/8/26 13:22:37

力扣 283 移动零的两种高效解法详解

目录方法一：两次遍历法方法二：单次遍历交换法两种方法对比在解决数组中的零移动到末尾的问题时，我们需要保持非零元素的顺序，并原地修改数组。以下是两种高效的解法及其详细分析。方法一：两次遍历法思路分析…...

编程日记 2025/8/26 22:14:00

代码随想录第18天：二叉树

一、修剪二叉树（Leetcode 669） 递归法 class Solution:def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:# 如果当前节点为空，直接返回空节点（递归终止条件）if root is None:return None# 如果…...

编程日记 2025/8/20 7:23:18

KMP算法核心笔记：前后缀本质与nextval实现

KMP算法核心笔记：前后缀本质与nextval实现核心疑问：为什么用「前后缀」而非「最大子串」？ 1. 结构唯一性前后缀限定在字符串首尾区域，最大子串可位于任意位置只有前后缀能保证滑动后的有效对齐 2. 移动确定性文本&#xf…...

编程日记 2025/8/26 22:11:32

Breeze 40A FOC 电调：Vfast 观测器技术赋能无人机精准动力控制

核心技术特性 1. 全新Vfast 观测器技术基于先进矢量控制算法（FOC 驱动），实现电机状态实时精准观测，适配性优于传统 FOC 方案，兼容主流无人机动力配置。高效算法设计，输出功率与力效超越多数方波电调&…...

编程日记 2025/8/26 22:14:02

如何处理ONLYOFFICE文档服务器与Java Web应用间的安全认证和授权

如何处理ONLYOFFICE文档服务器与Java Web应用间的安全认证和授权？ 处理 ONLYOFFICE 文档服务器与 Java Web 应用之间的安全认证和授权，通常涉及以下几个关键步骤和技术： 1. JWT (JSON Web Token) 认证启用 JWT： ONLYOFFICE 文档…...

编程日记 2025/8/21 21:09:36

手机上的PDF精简版：随时随地享受阅读

在移动互联网时代，随时随地阅读电子书和文档已经成为许多人的习惯。无论是学习、工作还是娱乐，一款好用的PDF阅读器都是必不可少的工具。今天，我们要介绍的思读PDF精简版，就是这样一款简洁而强大的PDF阅读工具，能够让…...

编程日记 2025/8/26 22:14:02

XCTF-web（一）

view_source F12ctrluctrlshiftiURL前添加：view-source:curl http://192.168.1.1robots 根据题目提示，查看一下robots.txt /flag_ls_h3re.php backup /index.php.bak ┌──(kali㉿kali)-[~] └─$ cat index.php.bak <html> <…...

编程日记 2025/8/26 22:14:00

字节跳动开源 Godel-Rescheduler：适用于云原生系统的全局最优重调度框架

背景在云原生调度中，一次调度往往无法解决所有问题，需要配合重调度来优化资源分配和任务摆放。传统的重调度框架主要集中在识别异常节点或任务，并通过迁移或删除来解决。然而，这些框架往往只能解决局部问题，无法提供…...

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

贪心算法day9（合并区间）

1.合并区间 56. 合并区间 - 力扣（LeetCode） 对于这种区间问题，我们应该先排序根据排序的结果总结一些规律，进而的得出解决该问题的策略。 class Solution {public static int[][] merge(int[][] intervals) {//第一步进行左端点…...

编程日记 2025/8/26 22:14:01

插件化设计，打造个性化音乐体验！

打工人们你们好！这里是摸鱼特供版~ 今天给大家带来一款超酷的音乐播放器——MusicFree，它不仅功能强大，还支持插件化设计，让你的音乐体验更加个性化！ 推荐指数：★★★★★ 1. 插件化设计功能强大&#…...

编程日记 2025/8/24 2:01:40

深入解析分类模型评估指标：ROC曲线、AUC值、F1分数与分类报告

标题：深入解析分类模型评估指标：ROC曲线、AUC值、F1分数与分类报告摘要： 在机器学习中，评估分类模型的性能是至关重要的一步。本文详细介绍了四个核心评估指标：ROC曲线、AUC值、F1分数和分类报告。通过对比这些指标…...

编程日记 2025/8/26 22:14:02

2025第16届蓝桥杯省赛之研究生组F题01串求解

2025第16届蓝桥杯省赛之研究生组F题01串求解一、题目概述二、解题思路2.1题目分析2.2解题思路三、求解代码3.1求解步骤3.1.1求解x所在的二进制位数区间3.1.2求解总位数为cnt的含1数3.1.3求解cnt1~x之间的含1数 3.2完整代码3.3代码验证四、小结一、题目概述给定一个由0,1,…...

编程日记 2025/8/19 10:02:47

【2-10】E1与T1

前言之前我们简单介绍了人类从电话线思维到如今的数据报分组交换思维过渡时期的各种技术产物，今天我们重点介绍 E1/T1技术。文章目录前言1. 产生背景2. T13. E14. SONET4.1 OC-14.2 OC-3 及其它 5. SDH5.1. STM-1 6. SONET VS SDH后记修改记录 1. 产生背景 E1/…...

编程日记 2025/8/21 5:08:35

2025 年蓝桥杯 Java B 组真题解析分享

今年是我第二次参加蓝桥杯软件类Java B组的比赛，虽然赛前做了不少准备，但真正坐在考场上时，还是有种熟悉又紧张的感觉。蓝桥杯的题目一向以“基础创新”著称，今年也不例外，每道题都考验着我们对算法的理解、代码实现能…...

编程日记 2025/8/17 20:45:14

IMX6ULL2025年最新部署方案2在Ubuntu24.04上编译通过Qt5.12.9且部署到IMX6ULL正点原子开发板上

IMX6ULL2025年最新部署方案2:在Ubuntu24.04上编译通过Qt5.12.9且部署到IMX6ULL正点原子开发板上前言本篇方案部署是笔者这几天除了打蓝桥杯以外，笔者在研究的东西，现在写道这里的时候，笔者已经成功的在Ubuntu24.04上，使用默…...

编程日记 2025/8/26 7:49:47

通过微信APPID获取小程序名称

进入微信公众平台，登录自己的小程序后台管理端，在“账号设置”中找到“第三方设置” 在“第三方设置”页面中，将页面拉到最下面，即可通过appid获取到这个小程序的名称信息...

编程日记 2025/8/17 18:41:26

混合开发部署实战：PyInstaller + .NET 8 + Docker全链路配置

文章目录一、PyInstaller打包Python环境1. 基础打包（Linux环境）2. 高级配置3. 验证打包结果二、.NET 8与Python的集成模式1. 进程调用（推荐方案）2. REST API通信三、Docker多阶段构建配置1. 完整Dockerfile示例2. 关键配置解析…...

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

使用 Sass 打造动态星空背景效果

在前端开发中，视觉效果越来越受到重视。本文将通过一个生动的示例，讲解如何利用 Sass 构建一个具有动态星空滚动效果的背景页面，同时也系统介绍 Sass 的核心功能与实践技巧。一、Sass 的作用 Sass（Syntactically Awesome Style …...

编程日记 2025/8/23 8:09:14

低空经济有哪些GIS相关岗位?

在低空经济中，GIS（地理信息系统）技术发挥着重要作用。GIS开发工程师负责开发、维护和优化与低空经济相关的GIS系统，如无人机起降场布局、空域管理、气象监测等。一般会参与二、三维GIS项目数据处理与前端开发，以及相关…...

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

Python 垃圾回收机制全解析：内存释放与优化

在编写高效、稳定的 Python 程序时，内存管理往往是一个被忽视但至关重要的领域。对于 Python 开发者来说，最初的学习曲线通常集中在语法、库使用和应用框架上，而对于内存管理和垃圾回收（GC，Garbage Collection&#xf…...

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

性能优化实践

4.1 大规模量子态处理的性能优化背景与问题分析量子计算中的大规模量子态处理（如量子模拟、量子态可视化）需要高效计算和实时渲染能力。传统图形API（如WebGL）在处理高维度量子态时可能面临性能瓶颈，甚至崩溃（如表格中14量子比特时WebGL的崩溃）。而现代API（如WebGPU…...

编程日记 2025/8/20 11:25:17

span https://github.com/open-telemetry/opentelemetry-cpp/blob/f987c9c094f276336569eeea85f17e361de5e518/sdk/src/trace/span.h 在 OpenTelemetry C 的 sdk/src/trace 目录中，不同的 span 定义和实现是为了支持追踪（Tracing）功能的多样…...

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

【JavaScript】二十一、日期对象

文章目录 1、实例化日期对象2、相关方法3、时间戳4、案例：毕业🎓倒计时效果 1、实例化日期对象获得当前时间 const date new Date()获得指定时间 const date new Date(2025-4-14 20:46:00) console.log(date)2、相关方法方法作用说明getFullYear…...

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

GIT工具学习【1】：新安装git预操作

目录 1.写在前面2.为常用指令配置别名3.初始化4.解决中文乱码问题 1.写在前面新安装git命令后，需要一些设置会用的比较的顺畅。这篇文章只要跟着做即可，至于原理，后面会写清楚的。 2.为常用指令配置别名 #新建一个.bashrc touch ~/.bash…...

编程日记 2025/8/26 22:11:30

docker安装ES

ES安装步骤 1. 创建docker网络，使其docker内部通信 2. 下载 | 导入镜像文件（ES Kibana） 3. 创建容器，并访问 4. 安装Ik分词器（es对中文并不友好，所以需要安装IK分词使其适配中文） 1. 创建docke…...

编程日记 2025/8/24 5:12:26

【控制学】控制学分类

【控制学】控制学分类文章目录 [TOC](文章目录) 前言一、工程控制论1. 经典控制理论2. 现代控制理论二、生物控制论三、经济控制论总结前言控制学是物理、数学与工程的桥梁提示：以下是本篇文章正文内容，下面案例可供参考一、工程控制论 1. 经典…...

编程日记 2025/8/26 22:14:02

人工智能应用开发中常见的工具、框架、平台的分类、详细介绍及对比

以下是人工智能应用开发中常见的工具、框架、平台的分类、详细介绍及对比： 一、工具（Tools） 定义：用于完成特定任务的软件或库，通常专注于开发流程中的某个环节（如数据处理、模型调试、部署等&#xff…...

编程日记 2025/8/25 14:44:46

Linux磁盘格式化(mkfs、mkfs.xfs、mkfs.ext4)、Linux文件系统的校验(xfs_repair、fsck_ext4)

在Linux系统中，磁盘格式化和文件系统校验是系统管理的重要任务。以下是关键步骤和命令的总结：磁盘格式化 1. 选择文件系统类型 XFS：适用于大文件和高并发场景，支持高性能和扩展性。ext4：成熟稳定的通用文件系统，适合大多数场景。2. 格式化命令通用格式： sudo mkfs -…...

编程日记 2025/8/26 22:14:00

Android学习总结之git篇

Git 的原理时，你可以从数据结构、对象存储、引用管理、分支与合并等方面结合源码进行分析。以下是详细介绍： 1. 基本数据结构和对象存储 Git 底层主要基于四种对象来存储数据：blob（数据块）、tree（树&…...

编程日记 2025/8/24 2:05:46

Python基础语法——类型

目录类型的意义动态类型静态类型类型的意义不同的类型,占用的内存空间是不同的. 占几个字节 int 默认是 4 个字节.动态扩容 float 固定 8 个字节 bool 一个字节就足够了 str 变长的不同的类型,对应能够进行的操作也是不同的 int/float, “” “-” “ * ” “/”——不能使…...

编程日记 2025/8/25 0:18:03

vue2中基于el-select封装一个懒加载下拉框

需求当下拉选项的数据量过大时，后端接口是分页格式返回数据。解决方案自定义封装一个懒加载下拉组件，每次滚动到底部时自动获取下一页数据，这样可有效防止数据量过大时造成组件卡顿。具体实现步骤 1、创建懒加载下拉选择组件 <t…...

编程日记 2025/8/26 14:00:18

uniapp的h5，打开的时候，标题会一闪而过应用名称，再显示当前页面的标题

问题： 微信小程序，通过webview打开了uniapp创建的h5，但是打开h5时，会先显示h5的应用名称，然后才切换为该页面的标题。过程： 查过很多资料，有说修改应用名称，有说设置navigationS…...

编程日记 2025/8/26 22:11:32

HarmonyOS 5 开发环境全解析：从搭建到实战

鸿蒙来了，从 1.0 到 5.0，它不再只是“华为的操作系统”，而是万物互联生态的核心驱动。作为开发者，你准备好拥抱这个全新时代了吗？ 你是否还在犹豫：HarmonyOS 5 开发门槛高不高？该用 DevEco Stu…...

编程日记 2025/8/25 23:00:23

2.2 函数返回值

1.回顾def def sum(x,y): return xy res sum(10,20) #调用函数 print(res) 2.函数的三个重要属性 -函数的类型：function -函数的ID：16进制的整数数值 -函数的值：封装在函数中的数据和代码 # - 函数是一块内存空间，通过…...

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

OpenAI发布GPT-4.1：开发者专属模型的深度解析 [特殊字符]

最近OpenAI发布了GPT-4.1模型，却让不少人感到困惑。今天我们就来深入剖析这个新模型的关键信息！ 重要前提：API专属模型 💻 首先需要明确的是，GPT-4.1仅通过API提供，不会出现在聊天界面中。这是因为该模型主…...

编程日记 2025/8/17 18:46:53

Cython中操作C++字符串

使用Cython开发Python扩展模块-CSDN博客中文末对python代码做了部分C优化，并提及未对字符串类型做优化，并且提到如果不是真正搞懂了C字符串的操作和Python的C API中与字符串相关的知识，最好不要动Python中的字符串类型。为了搞明白在Cython中…...

编程日记 2025/8/20 7:31:28

Dify插件内网安装，解决Dify1.x插件安装总失败问题，手把手教你暴力破解：从镜像源到二进制打包全攻略

背景自从dify升级到1.0以后，所有的工具和模型都改成了插件化，需要进行插件的安装。在手撕Dify1.x插件报错！从配置到网络到Pip镜像，一条龙排雷实录已经指出了dify在线安装插件的各种问题。首发地址在前面的几个版本中&…...

编程日记 2025/8/24 14:36:13

二极管详解：特性参数、选型要点与分类

一、二极管的基本定义二极管（Diode） 是由半导体材料（如硅、锗）构成的双端器件，核心特性是单向导电性。其结构基于PN结，正向偏置导通，反向偏置截止。核心功能： 整流（交…...

编程日记 2025/8/19 5:12:49

BufferedOutputStream 终极解析与记忆指南

BufferedOutputStream 终极解析与记忆指南一、核心本质 BufferedOutputStream 是 Java 提供的缓冲字节输出流，继承自 FilterOutputStream，通过内存缓冲区显著提升 I/O 性能。核心特性速查表特性说明继承链OutputStream → FilterOutputStream → …...

编程日记 2025/8/25 14:15:29

Google政策大更新：影响金融，新闻，社交等所有类别App

Google Play 4月10日迎来了2025年第一次大版本更新，新政主要涉及金融（个人贷款），新闻两个行业。但澄清内容部分却使得所有行业都需进行一定的更新。下面，我们依次从金融（个人贷款），…...

编程日记 2025/8/23 4:23:34

【Linux网络与网络编程】10.网络层协议IP

前言我们之前谈的主机B把数据传递给主机C过程都是黑盒式的，即并没有考虑它的中间过程。本篇博客和下一篇博客将要考虑的问题是：主机B和主机C并不是直接连接的，主机B想要把数据传输给主机C需要经过若干路由器的。我们就引出了两个问题&#x…...

编程日记 2025/8/17 20:18:03

Docker 搭建 RabbitMQ

Docker 搭建 RabbitMQ 前言一、准备工作二、设置目录结构三、编写启动脚本四、Host 网络模式 vs Port 映射模式1. Host 网络模式2. Port 映射模式五、端口配置对比六、配置示例七、查看与管理八、扩展与高可用九、常用命令前言在现代微服务与分布式架构中，Rabbi…...

编程日记 2025/8/26 22:14:01

浏览器自动化检测对抗：修改navigator.webdriver属性的底层实现

一、背景介绍：你被自动化检测拒之门外了吗？ 在使用 Selenium 或 Playwright 等浏览器自动化工具爬取数据时，经常会遇到「被检测」问题，尤其像 Amazon 这样反爬策略严密的网站。常见的检测机制之一就是检查 JavaScript 中的 navig…...

编程日记 2025/8/23 8:24:47

聊聊Spring AI Alibaba的DocumentParser

序本文主要研究一下Spring AI Alibaba的DocumentParser DocumentParser spring-ai-alibaba-core/src/main/java/com/alibaba/cloud/ai/document/DocumentParser.java public interface DocumentParser {/*** Parses a given {link InputStream} into a {link Document}. T…...

编程日记 2025/8/26 12:54:30

用css给div列表加个序号

用 CSS 的 counter 相关属性来为列表添加序号。以下是具体的代码，我将以 HTML 文件的形式提供，并且会运行展示效果： .as-div {// counter-reset: my-counter; /* 计数器名称是my-counter */// counter-reset: small-apple; /* 计数器名称是s…...

编程日记 2025/8/24 1:10:27

CSS标签选择器与类选择器

CSS标签选择器标签选择器（元素选择器）是最基本的选择器之一，用于选择HTML文档中的特定标签元素并应用样式。它使用HTML标签名称作为选择器，选择匹配该标签的所有元素。作用：通过HTML标签名选择元素以下是CSS标签选…...

编程日记 2025/8/21 4:29:41

（51单片机）LCD显示日期时间时钟（DS1302时钟模块教学）（LCD1602教程）

目录源代码 main.c LCD1602.c LCD1602.h DS1302.c DS1302.h 代码解析与教程： LCD1602模块 DS1302模块效果视频： 源代码如上图将5个文放在Keli5 中即可，然后烧录在单片机中就行了烧录软件用的是STC-ISP，不知道怎么安装的…...

编程日记 2025/8/17 1:36:47

编译原理（自考13007）

资源内容大纲概述...

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

C#Winform程序将子窗体嵌入容器方法

private void OpenForm(Form childFrom) { //首先判断容器中是否有其他的窗体 foreach (Control item in this.panelRight.Controls) { if (item is Form) { ((Form)item).Close(); } } //嵌入新的窗体 childFrom.TopLevel false;//将子窗体设置成非顶级控件 childFrom.Parent…...

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

判断一个图是不是树

问题描述

算法解析

判断环

判断节点数和边数的关系

判断连通性

相关文章：