【力扣每日一题】2023.8.31 一个图中连通三元组的最小度数
目录
题目:
示例:
分析:
代码:
题目:

示例:

分析:
题目给我们一个无向图,要我们找出三个节点,这三个节点他们两两相连,这三个节点除了连接到对方的其他线被称为连通三元组的度数,问我们图中最小的三元组度数是多少。
我的第一个想法就是使用map来构建图,然后遍历每个节点,再遍历每个节点的相邻节点,再遍历每个节点的相邻节点的相邻节点,如果节点的相邻节点的相邻节点是该节点,那么我们就找到了连通三元组,他们总体的度数-6就是连通三元组的度数。因为三元组中每个节点为了连通另外两个节点,都需要花费两个度,而剩余的度就是连接其他非本三元组的节点了,所以连通三元组的度数就是三个节点的总度数-2*3。

不过这么做就超时了,因为同一个三元组我们会重复遍历三次,每个节点我们都会遍历寻找包括它的连通三元组。虽然这种方式超时了,但也不失为一种方法,代码在下面,可以参考。
那么直接构建图不行,我们可以构建图的邻接矩阵。
我们另外再拿一个数组来存放每个节点的度数。
邻接矩阵用来判断三个点是否是相互连通的,度数数组用来计算连通三元组的度数。

代码:
class Solution {
public:int minTrioDegree(int n, vector<vector<int>>& edges) {//超时unordered_map<int,unordered_set<int>>m;for(auto edge:edges){ //构建图if(m.find(edge[0])==m.end()) m[edge[0]]=unordered_set<int>();if(m.find(edge[1])==m.end()) m[edge[1]]=unordered_set<int>();m[edge[0]].insert(edge[1]);m[edge[1]].insert(edge[0]);}int res=INT_MAX;for(auto& i:m){ //取出每个节点for(auto& j: i.second){ //取出相连的节点集for(auto& k: m[j]){ //取出相连的节点的相连结果集if(m[k].count(i.first)){ //若是等于第一个节点,那么表示这仨节点相互连通res=min(res,static_cast<int>(i.second.size()+m[j].size()+m[k].size()-6));}}}}return res==INT_MAX?-1:res;//构建邻接矩阵 int res=INT_MAX;vector<vector<int>>pic(n+1,vector<int>(n+1,0)); //连通矩阵vector<int>du(n+1,0); //每个点的度for(auto& edge: edges){ //构建邻接矩阵以及获取每个节点的度pic[edge[0]][edge[1]]=1;pic[edge[1]][edge[0]]=1;du[edge[0]]++;du[edge[1]]++;} for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){for(int k=j+1;k<=n;k++){//遍历每个节点,找到相互连通的三个节点,度数之和-6就是连通三元组的读度数if(pic[i][j] && pic[j][k] && pic[i][k]) res=min(res,du[i]+du[j]+du[k]-6);}}}return res==INT_MAX?-1:res;}
};
相关文章:
【力扣每日一题】2023.8.31 一个图中连通三元组的最小度数
目录 题目: 示例: 分析: 代码: 题目: 示例: 分析: 题目给我们一个无向图,要我们找出三个节点,这三个节点他们两两相连,这三个节点除了连接到对方的其他线…...
C语言--volatile
volatile 1、介绍 volatile是一个类型修饰符(type specifier)。它是被设计用来修饰被不同线程访问和修改的变量。如果没有volatile,基本上会导致这样的结果:要么无法编写多线程程序,要么编译器失去大量优化的机会。 …...
技术深入解析与教程:网络安全技术探秘
第一章:引言 在当今数字化时代,网络安全已经成为了重要议题。随着各种信息和业务在网络上的传输与存储,安全问题也日益突出。本文将带您深入探讨网络安全领域中的关键技术,涵盖渗透测试、漏洞挖掘以及恶意软件分析等方面…...
Android studio 实现生成二维码和扫描二维码
效果图 build.gradle(:app)添加依赖 dependencies {implementation com.google.zxing:core:3.3.3implementation com.journeyapps:zxing-android-embedded:3.6.0implementation com.google.zxing:javase:3.0.0 }Manifests.xml <uses-permission android:name"android…...
Linux中7种文件类型
Linux中文件类型 Linux中一切皆为文件。 查看文件类型(输入以下命令根据第一列的第一个字符可区别文件类型) ls -l目录文件 第一个字符为d 类似于Windows文件夹。 链接文件(软链接) 第一个字符为l 例如Windows的快捷方式&…...
基础算法--快速排序
快速排序 算法原理 1. 取一个元素p(第一个元素,最后一个元素,中间元素,随机 都可以),使元素p归位。 2. 列表被p分成两部分,左边都比p小,右边都比p大。 3. 递归完成排序。 动态演示 python代码实现 import…...
机器学习的第一节基本概念的相关学习
目录 1.1 决策树的概念 1.2 KNN的概念 1.2.1KNN的基本原理 1.2.2 流程: 1.2.3 优缺点 1.3 深度学习 1.4 梯度下降 损失函数 1.5 特征与特征选择 特征选择的目的 1.6 python中dot函数总结 一维数组的点积: 二维数组(矩阵)的乘法&am…...
Python 之__name__的用法以及解释
文章目录 介绍代码 介绍 __name__ 是一个在 Python 中特殊的内置变量,用于确定一个 Python 文件是被直接运行还是被导入为模块。 文件作为模板导入,则其 __name__属性值被自动设置为模块名 文件作为程序直接运行,则__name__属性属性值被自动设…...
【FPGA零基础学习之旅#12】三线制数码管驱动(74HC595)串行移位寄存器驱动
🎉欢迎来到FPGA专栏~三线制数码管驱动 ☆* o(≧▽≦)o *☆嗨~我是小夏与酒🍹 ✨博客主页:小夏与酒的博客 🎈该系列文章专栏:FPGA学习之旅 文章作者技术和水平有限,如果文中出现错误,希望大家能指…...
networkX-03-连通度、全局网络效率、局部网络效率、聚类系数计算
文章目录 1.连通度1.1 检查图是否连通1.2 检查有向图是否为强连通1.3 点连通度、边连通度: 2.网络效率2.1全局效率2.2 局部效率2.2.1 查找子图2.2.3 局部效率源码分析 3.聚类系数(Clustering Coefficient)3.1 聚类系统源码分析 教程仓库地址&…...
【深入解读Redis系列】Redis系列(五):切片集群详解
首发博客地址 https://blog.zysicyj.top/ 系列文章地址[1] 如果 Redis 内存很大怎么办? 假设一台 32G 内存的服务器部署了一个 Redis,内存占用了 25G,会发生什么? 此时最明显的表现是 Redis 的响应变慢,甚至非常慢。 这…...
无涯教程-JavaScript - NORMDIST函数
NORMDIST函数替代Excel 2010中的NORM.DIST函数。 描述 该函数返回指定均值和标准差的正态分布。此功能在统计中有非常广泛的应用,包括假设检验。 语法 NORMDIST(x,mean,standard_dev,cumulative)争论 Argument描述Required/OptionalXThe value for which you want the dis…...
递归应用判断是否循环引用
var data await _IDBInstance.DBOperation.QueryAsync<FormulaReference>(sql);//向上查询引用公式 List<FormulaReference> GetSonNode(long id, List<FormulaReference> nodeList, List<long> path null){if (path null){path new List<long…...
使用nginx-lua配置统一url自动跳转到hadoop-ha集群的active节点
下载安装nginx所用的依赖 yum -y install gcc zlib zlib-devel pcre-devel openssl openssl-devel下载nginx wget http://nginx.org/download/nginx-1.12.2.tar.gz tar -xvf nginx-1.12.2.tar.gz稍后安装nginx 安装lua语言 yum install readline-develcurl -R -O http://w…...
AJAX学习笔记2发送Post请求
AJAX学习笔记1发送Get请求_biubiubiu0706的博客-CSDN博客 继续 AJAX发送POST请求 无参数 测试 改回来 测试 AJAX POST请求 请求体中提交参数 测试 后端打断点 如何用AJAX模拟form表单post请求提交数据呢? 设置请求头必须在open之后,send之前 请求头里的设置好比…...
产品团队的需求分析指南
需求分析是软件开发流程中需求识别与管理的关键环节,需求分析的目的在于确保所有产品需求准确地代表了利益相关者的需求和要求。选择合适的需求分析方式可以帮助我们获取准确的产品需求,从而保证我们所交付的成果与利益相关者预期相符。 一、什么是需求…...
Python算法——排序算法(冒泡、选择、插入、快速、堆排序、并归排序、希尔、计数、桶排序、基数排序)
本文章只展示代码实现 ,原理大家可以参考: https://zhuanlan.zhihu.com/p/42586566 一、冒泡排序 def bubble_sort(lst):for i in range(len(lst) - 1): # 表示第i趟exchange False # 每一趟做标记for j in range(len(lst)-i-1): # 表示箭头if ls…...
[Linux]文件描述符(万字详解)
[Linux]文件描述符 文章目录 [Linux]文件描述符文件系统接口open函数close函数write函数read函数系统接口与编程语言库函数的关系 文件描述符文件描述符的概念文件数据交换的原理理解“一切皆文件”进程默认文件描述符文件描述符和编程语言的关系 重定向输出重定向输入重定向追…...
RenderTarget导出成图片,CineCamera相机
一、获取Cinecamera相机图像 1.1、启用UE自带插件 1.2、在UE编辑器窗口栏找到Composure合成,打开窗口 1. 3、右键空白处,新建合成,默认名称为 0010_comp;再右键新建的 0010_comp,新建图层元素 CGLayer层,默…...
深入探讨Java虚拟机(JVM):执行流程、内存管理和垃圾回收机制
目录 什么是JVM? JVM 执行流程 JVM 运行时数据区 堆(线程共享) Java虚拟机栈(线程私有) 什么是线程私有? 程序计数器(线程私有) 方法区(线程共享) JDK 1.8 元空…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
