【C++图论】1761. 一个图中连通三元组的最小度数|2005
本文涉及知识点
C++图论
LeetCode1761. 一个图中连通三元组的最小度数
给你一个无向图,整数 n 表示图中节点的数目,edges 数组表示图中的边,其中 edges[i] = [ui, vi] ,表示 ui 和 vi 之间有一条无向边。
一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。
连通三元组的度数 是所有满足此条件的边的数目:一个顶点在这个三元组内,而另一个顶点不在这个三元组内。
请你返回所有连通三元组中度数的 最小值 ,如果图中没有连通三元组,那么返回 -1 。
示例 1:
输入:n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
输出:3
解释:只有一个三元组 [1,2,3] 。构成度数的边在上图中已被加粗。
示例 2:
输入:n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
输出:0
解释:有 3 个三元组:
- [1,4,3],度数为 0 。
- [2,5,6],度数为 2 。
- [5,6,7],度数为 2 。
提示:
2 <= n <= 400
edges[i].length == 2
1 <= edges.length <= n * (n-1) / 2
1 <= ui, vi <= n
ui != vi
图中没有重复的边。
图论
枚举三个节点(i,j,k) i <j <k ,时间复杂度:O(nnn/6),如果细节没处理好,可能会超时。
连接矩阵mat 记录i,j是否连通。
deg[i]记录和i连接的边数。
(i,j,k)的度数就是deg(i)+deg(j)+deg(k)-6
代码
核心代码
class Solution {public:int minTrioDegree(int n, vector<vector<int>>& edges) {int ans = INT_MAX;vector<vector<bool>> mat(n, vector<bool>(n));vector<int> deg(n);for (const auto& v : edges) {mat[v[0] - 1][v[1] - 1] = true;mat[v[1] - 1][v[0] - 1] = true;deg[v[0] - 1]++;deg[v[1] - 1]++;}for(int i = 0 ; i < n ; i++ )for(int j = i+1; j < n; j++ )for (int k = j + 1; k < n; k++) {if (!mat[i][j] || !mat[i][k] || !mat[j][k])continue;ans = min(ans, deg[i] + deg[j] + deg[k] -6);}return INT_MAX == ans ? -1 : ans;}};
单元测试
int n;vector<vector<int>> edges;TEST_METHOD(TestMethod11){n = 6, edges = { {1,2},{1,3},{3,2},{4,1},{5,2},{3,6} };auto res = Solution().minTrioDegree(n, edges);AssertEx(3, res);}TEST_METHOD(TestMethod12){n = 7, edges = { {1,3},{4,1},{4,3},{2,5},{5,6},{6,7},{7,5},{2,6} };auto res = Solution().minTrioDegree(n, edges);AssertEx(0, res);}TEST_METHOD(TestMethod13){n = 3, edges = { {1,2},{2,3},{1,3} };auto res = Solution().minTrioDegree(n, edges);AssertEx(0, res);}
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。
相关文章:
【C++图论】1761. 一个图中连通三元组的最小度数|2005
本文涉及知识点 C图论 LeetCode1761. 一个图中连通三元组的最小度数 给你一个无向图,整数 n 表示图中节点的数目,edges 数组表示图中的边,其中 edges[i] [ui, vi] ,表示 ui 和 vi 之间有一条无向边。 一个 连通三元组 指的是 …...
【力扣:新动计划,编程入门 —— 题解 ③】
—— 25.1.26 231. 2 的幂 给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。 如果存在一个整数 x 使得 n 2x ,则认为 n 是 2 的幂次方。 示例 1: 输入:…...
「全网最细 + 实战源码案例」设计模式——工厂方法模式
核心思想 简单工厂模式是一种创建者模式,它通过一个工厂类负责创建不同类型的对象,根据传入的参数决定实例化的具体类,也被称为“静态工厂方法”模式,因为工厂方法通常是静态的。 结构 1. 工厂类: 提供一个静态方法…...
SpringBoot使用MockMVC通过http请求controller控制器调用测试
说明 在Spring Boot中编写测试控制器调用是一个常见的需求,通常使用Spring的测试框架来完成。Spring Boot提供了多种方式来测试控制器,包括使用MockMvc进行模拟HTTP请求和响应的测试。 基本示例 1. 创建Spring Boot项目 首先,确保你已经创建了一个Spring Boot项目。如果…...
电子应用设计方案105:智能家庭AI拖把系统设计
智能家庭 AI 拖把系统设计 一、引言 智能家庭 AI 拖把系统旨在为用户提供更高效、便捷和智能化的地面清洁解决方案,减轻家务劳动负担。 二、系统概述 1. 系统目标 - 自动清洁地面,包括吸尘、拖地和擦干功能。 - 智能识别地面材质和污渍程度,…...
Android13源码下载和编译过程详解
前言 作为Android开发者人人都应该有一份自己Android源码,这样我们就可以随时对自己有疑惑的地方通过亲手调试来加强理解 一 源码下载 1.1 配置要求 官方推荐配置请参考:AOSP使用入门文档,重点有如下几项: 1.1.1 硬件配置要求 至少需要…...
Greenplum临时表未清除导致库龄过高处理
1.问题 Greenplum集群segment后台日志报错 2.回收库龄 master上执行 vacuumdb -F -d cxy vacuumdb -F -d template1 vacuumdb -F -d rptdb 3.回收完成后检查 仍然发现segment还是有库龄报警警告信息发出 4.检查 4.1 在master上检查库年龄 SELECT datname, datfrozen…...
SD-WAN站点和客户端的区别
很多用户在使用比扬云SD-WAN的时候不清楚站点和员工客户端的区别,尤其是很多从ZeroTier迁移过来的用户,这篇文章我们会详细介绍比扬云SD-WAN的站点和客户端使用场景。 ZeroTier只有客户端,没有站点,但是有路由配置,允…...
Arduino大师练成手册 -- 控制 MH-SD 卡模块
要在 Arduino 上控制 MH-SD 卡模块,你可以按照以下步骤进行: 硬件连接 VCC:连接到 Arduino 的 3.3V 或 5V 引脚(根据模块的要求)。 GND:连接到 Arduino 的 GND 引脚。 CS:连接到 Arduino 的…...
【MQ】RabbitMq的可靠性保证
消息队列中的可靠性主要是分为三部分: 消息不丢失:确保消息从生产者发送到消费者消息不丢失消息不重复:确保消息不被重复消费消息顺序性:确保消费的顺序性 解决方案主要有以下几部分: 消息不丢失 生产者确认机制持久…...
自签证书的dockerfile中from命令无法拉取镜像而docker的pull命令能拉取镜像
问题现象: docker pull images拉取镜像正常 dockerfile中的from命令拉取镜像就会报出证书错误。报错信息如下: [bjxtbwj-kvm-test-jenkins-6-243 ceshi_dockerfile]$ docker build . [] Building 0.4s (3/3) FINISHED …...
LAPD协议
实现LAPD(Link Access Procedure on the D-channel)协议的具体步骤和代码示例会比较复杂,通常涉及到底层网络编程和对ISDN协议的深入理解。以下是一个更详细的实现指导,主要集中在C/C环境中。 环境准备 确保你有一个支持ISDN的开发…...
jupyter版本所引起的扩展插件问题
文章目录 如何永久切换python安装源为https://mirrors.aliyun.com/pypi/simple方法一:通过配置文件永久设置(推荐)步骤 1:创建或修改 pip 配置文件步骤 2:验证配置是否生效 方法二:通过命令行直接配置效果验…...
连接 OpenAI 模型:基础操作
在这一部分中,我们将介绍如何连接 OpenAI 模型,设置 API 密钥,并使用 Spring AI 的 ChatClient 与 OpenAI 模型进行简单的对话。Spring AI 为集成 OpenAI 模型提供了方便的工具,使得开发者能够更轻松地与 GPT 系列模型进行交互。 …...
Vue.js组件开发-实现对视频预览
在 Vue 中实现视频文件预览 实现步骤 创建 Vue 组件:构建一个 Vue 组件用于处理视频文件的选择和预览。文件选择:添加一个文件输入框,允许用户选择视频文件。读取文件:监听文件选择事件,使用 FileReader API 读取所选…...
基于 Arduino Uno 和 RFID-RC522 的 RFID 卡号读取技术详解
引言 射频识别(RFID)技术因其非接触式、高效性和低成本的特点,广泛应用于门禁系统、物流管理和智能设备等领域。本文将通过 Arduino Uno 和 MFRC522 RFID 模块,手把手教你实现 RFID 卡号的读取,并提供完整的代码解析和…...
AI Agent的测试与监控:保障稳定性的实战经验
在前面的文章中,我们讨论了 AI Agent 的各个核心模块。今天,我想聊聊如何保障 AI Agent 的稳定性。说实话,这个话题我一直很关注,因为在生产环境中,稳定性往往比功能更重要。 从一次线上事故说起 还记得去年一个深夜…...
Servlet项目依赖管理
一、Servlet 相关技术选型 思路: 先选择 Servlet 容器,再找支持当前 JDK 版本的 Servlet 容器版本。 已知Servlet容器有两种市场占用率较高,Tomcat&Jetty。接下来分别按照上述思路进行选择容器版本。 Tomcat 官网: https://tomcat.apache.org/ 版本…...
戴尔电脑设置u盘启动_戴尔电脑设置u盘启动多种方法
最近有很多网友问,戴尔台式机怎么设置u盘启动,特别是近两年的戴尔台式机比较复杂,有些网友不知道怎么设置,其实设置u盘启动有两种方法,下面小编教大家戴尔电脑设置u盘启动方法。 戴尔电脑设置u盘启动方法一、戴尔进入b…...
大数据治理实战指南:数据质量、合规与治理架构
📝个人主页🌹:一ge科研小菜鸡-CSDN博客 🌹🌹期待您的关注 🌹🌹 引言 随着企业数字化转型的加速,大数据已成为驱动业务决策的核心资产。然而,数据治理的缺失或不完善&…...
2025年01月26日Github流行趋势
项目名称:onlook 项目地址url:https://github.com/onlook-dev/onlook项目语言:TypeScript历史star数:4871今日star数:207项目维护者:Kitenite, drfarrell, iNerdStack, abhiroopc84, apps/dependabot项目简…...
03-画P封装(制作2D+添加3D)
画P封装的方法2D制作3D添加 使用P封装自己画0603格式的电阻的P封装1. 看规格书,找参数2. 创建一个新的P封装3. 灯泡两侧放焊盘4.设置焊盘大小和形状5.根据坐标定义中间间隔: L/2原则6. 画最外层丝印(丝印层直接围住即可)7.在平面的P封装上,添加3D立体封装库 立创商城下载P封装向…...
WPF5-x名称空间
1. x名称空间2. x名称空间内容3. x名称空间内容分类 3.1. x:Name3.2. x:Key3.3. x:Class3.4. x:TypeArguments 4. 总结 1. x名称空间 “x名称空间”的x是映射XAML名称空间时给它取的名字(取XAML的首字母),里面的成员(如x:Class、…...
UDP 广播组播点播的区别及联系
1、网络IP地址的分类 组播地址是分类编址的IPv4地址中的D类地址,又叫多播地址,他的前四位必须是1110,所以网络地址的二进制取值范围是11100000~11101111对应的十进制为 224~~239。所以以224~239开头的网络地址都是组播地址。 组播地址的功能…...
SSM开发(二) MyBatis两种SQL配置方式及其对比
目录 一、MyBatis两种SQL配置方式 二、使用XML映射文件配置SQL语句 三、使用注解配置SQL语句 四、两种方式对比 总结 1、注解 2、XML配置 五、MyBatis多数据源的两种配置方式 参考 一、MyBatis两种SQL配置方式 MyBatis 提供了两种方式来配置SQL语句:注解(如 @Select…...
leetcode——删除链表的倒数第N个节点(java)
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head [1,2,3,4,5], n 2 输出:[1,2,3,5] 示例 2: 输入:head [1], n 1 输出:[] 示例 3…...
SpringBoot支持动态更新配置文件参数
前言 博主介绍:✌目前全网粉丝3W,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。 涵盖技术内容:Java后端、大数据、算法、分布式微服务、中间件、前端、运维等。 博主所有博客文件…...
DeepSeek-R1,用Ollama跑起来
# DeepSeek-R1横空出世,超越OpenAI-o1,教你用Ollama跑起来 使用Ollama在本地运行DeepSeek-R1的操作指南。 DeepSeek-R1作为第一代推理模型,在数学、代码和推理任务上表现优异,与OpenAI-o1模型不相上下。 将此类模型部署到本地&am…...
基于OpenCV实现的答题卡自动判卷系统
一、图像预处理 🌄 二、查找答题卡轮廓 📏 三、透视变换 🔄 四、判卷与评分 🎯 五、主函数 六、完整代码+测试图像集 总结 🌟 在这篇博客中,我将分享如何使用Python结合OpenCV库开发一个答题卡自动判卷系统。这个系统能够自动从扫描的答题卡中提取信…...
VS Code i18n国际化组件代码code显示中文配置 i18n ally
VUE项目做i18n国际化之后,代码中的中文都变成了code这时的代码就会显得非常难读,如果有一个插件能把code转换成中文显示就好了 vscode插件搜索“i18n ally” 在项目根文件夹下创建文件:.vscode/settings.json settings.json 内容如下 {"…...
后盾人JS--闭包明明白白
延伸函数环境生命周期 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title> <…...
[ Spring ] Spring Cloud Alibaba Aliyun OSS 2025
文章目录 Declare PluginsIntroduce DenpendenciesOSS ApplicationOSS ConfigOSS Controller Declare Plugins pluginManagement {repositories {gradlePluginPortal()google()mavenCentral()} }dependencyResolutionManagement {repositoriesMode RepositoriesMode.PREFER_S…...
自定义数据集使用框架的线性回归方法对其进行拟合
代码 import torch import numpy as np import torch.nn as nncriterion nn.MSELoss()data np.array([[-0.5, 7.7],[1.8, 98.5],[0.9, 57.8],[0.4, 39.2],[-1.4, -15.7],[-1.4, -37.3],[-1.8, -49.1],[1.5, 75.6],[0.4, 34.0],[0.8, 62.3]])x_data data[:, 0] y_data data…...
工业数据分析:解锁工厂数字化的潜力
工业数据分析:解锁工厂数字化的潜力 引言 工业数据分析是工业4.0时代的核心技术之一。从生产设备的传感器数据,到供应链的物流信息,工业环境中每天都会产生海量数据。这些数据蕴藏着巨大的潜力,能够帮助企业优化生产流程、降低运营成本、提高产品质量。 然而,如何高效地…...
HTML5使用favicon.ico图标
目录 1. 使用favicon.ico图标 1. 使用favicon.ico图标 favicon.ico一般用于作为网站标志,它显示在浏览器的地址栏或者标签上 制作favicon图标 选择一个png转ico的在线网站,这里以https://www.bitbug.net/为例。上传图片,目标尺寸选择48x48&a…...
基于C++的DPU医疗领域编程初探
一、大型医院数据处理困境与 DPU 的崛起 在数字化浪潮的席卷下,医疗行业正经历着深刻变革,大型医院作为医疗服务的核心枢纽,积累了海量的数据,涵盖患者的基本信息、诊断记录、检验报告、影像资料等多个维度。这些数据不仅规模庞大,而且增长速度迅猛,传统的中央处理器(C…...
计算机网络 (62)移动通信的展望
一、技术发展趋势 6G技术的崛起 内生智能:6G将强调自适应网络架构,通过AI驱动的智能算法提升通信能力。例如,基于生成式AI的6G内生智能架构将成为重要研究方向,实现低延迟、高效率的智能通信。信息编码与调制技术:新型…...
TCP/IP 协议:互联网通信的基石
TCP/IP 协议:互联网通信的基石 引言 TCP/IP协议,全称为传输控制协议/互联网协议,是互联网上应用最为广泛的通信协议。它定义了数据如何在网络上传输,是构建现代互联网的基础。本文将深入探讨TCP/IP协议的原理、结构、应用以及其在互联网通信中的重要性。 TCP/IP 协议概述…...
Linux 基础2
Linux中有哪些常用命令 1.alias 给命令起别名 2.cat 显示文本内容 3.cd 修改当前路径 4.chmod 修改文件访问权限 5.chown 修改文件所有者 6.clear 清屏 7.cp 拷贝文件 8.df 查看文件系统信息 9.diff 比较两文件的异同 10.dpkg 手工安装软件包 11.echo 显示字符串 12.find 查找…...
关于java实现word(docx、doc)转html的解决方案
最近在研究一些关于文档转换格式的方法,因为需要用在开发的一个项目上,所以投入了一些时间,给大家聊下这块逻辑及解决方案。 一、关于word转换html大致都有哪些方法? (1)使用 Microsoft Word 导出 其实该…...
MongoDB部署模式
目录 单节点模式(Standalone) 副本集模式(Replica Set) 分片集群模式(Sharded Cluster) MongoDB有多种部署模式,可以根据业务需求选择适合的架构和部署方式。 单节点模式(Standa…...
[STM32 标准库]定时器输出PWM配置流程 PWM模式解析
前言: 本文内容基本来自江协,整理起来方便日后开发使用。MCU:STM32F103C8T6。 一、配置流程 1、开启GPIO,TIM的时钟 /*开启时钟*/RCC_APB1PeriphClockCmd(RCC_APB1Periph_TIM2, ENABLE); //开启TIM2的时钟RCC_APB2PeriphClockC…...
算法每日双题精讲 —— 二分查找(寻找旋转排序数组中的最小值,点名)
🌟快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。 🌟 别再犹豫了!快来订阅我们的算法每日双题精讲专栏,一起踏上算法学习的精彩之旅吧💪 在算法的…...
哈希表的使用
哈希表的概念:哈希表的核心是哈希函数,它接受一个键作为输入,经过一系列计算后返回一个整数,这个整数就是该键对应的存储位置(索引)。理想情况下,不同的键应该映射到不同的存储位置,…...
(一)QT的简介与环境配置WIN11
目录 一、QT的概述 二、QT的下载 三、简单编程 常用快捷键 一、QT的概述 简介 Qt(发音:[kjuːt],类似“cute”)是一个跨平台的开发库,主要用于开发图形用户界面(GUI)应用程序,…...
Qt监控系统辅屏预览/可以同时打开4个屏幕预览/支持5x64通道预览/onvif和rtsp接入/性能好
一、前言说明 在监控系统中,一般主界面肯定带了多个通道比如16/64通道的画面预览,随着电脑性能的增强和多屏幕的发展,再加上现在监控摄像头数量的增加,越来越多的用户希望在不同的屏幕预览不同的实时画面,一个办法是打…...
Python元组详解:不可变序列的魅力
Python元组详解:不可变序列的魅力 在Python中,元组(Tuple)是一种非常重要的数据结构。它与列表(List)类似,但有一个关键的区别:元组是不可变的。这意味着一旦创建了一个元组&#x…...
Qt5离线安装包无法下载问题解决办法
想在电脑里装一个Qt,但是直接报错。果然还是有解决办法滴。 qt download from your ip is not allowed Qt5安装包下载办法 方法一:简单直接,直接科学一下,不过违法行为咱不做,遵纪守法好公民(不过没办法阻…...
【蓝桥杯】43695.填字母游戏
题目描述 小明经常玩 LOL 游戏上瘾,一次他想挑战 K 大师,不料 K 大师说: “我们先来玩个空格填字母的游戏,要是你不能赢我,就再别玩 LOL 了”。 K 大师在纸上画了一行 n 个格子,要小明和他交替往其中填入…...
GD32的SPI程序读写程序,SPI特性研究
拿到一个SPI芯片的时序图: 能够知道这个过程需要24位,因此SPI的的帧长度设置为8位,然后读写3次。 spi_init_struct.frame_size SPI_FRAMESIZE_8BIT;如果帧长度设置为16位,读写两次就有32位了。 当然也可以设置帧长度为…...