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

【力扣每日一题】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 一个图中连通三元组的最小度数

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目给我们一个无向图&#xff0c;要我们找出三个节点&#xff0c;这三个节点他们两两相连&#xff0c;这三个节点除了连接到对方的其他线…...

C语言--volatile

volatile 1、介绍 volatile是一个类型修饰符&#xff08;type specifier&#xff09;。它是被设计用来修饰被不同线程访问和修改的变量。如果没有volatile&#xff0c;基本上会导致这样的结果&#xff1a;要么无法编写多线程程序&#xff0c;要么编译器失去大量优化的机会。 …...

技术深入解析与教程:网络安全技术探秘

第一章&#xff1a;引言 在当今数字化时代&#xff0c;网络安全已经成为了重要议题。随着各种信息和业务在网络上的传输与存储&#xff0c;安全问题也日益突出。本文将带您深入探讨网络安全领域中的关键技术&#xff0c;涵盖渗透测试、漏洞挖掘以及恶意软件分析等方面&#xf…...

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中一切皆为文件。 查看文件类型&#xff08;输入以下命令根据第一列的第一个字符可区别文件类型&#xff09; ls -l目录文件 第一个字符为d 类似于Windows文件夹。 链接文件&#xff08;软链接&#xff09; 第一个字符为l 例如Windows的快捷方式&…...

基础算法--快速排序

快速排序 算法原理 1. 取一个元素p(第一个元素&#xff0c;最后一个元素&#xff0c;中间元素&#xff0c;随机 都可以)&#xff0c;使元素p归位。 2. 列表被p分成两部分&#xff0c;左边都比p小&#xff0c;右边都比p大。 3. 递归完成排序。 动态演示 python代码实现 import…...

机器学习的第一节基本概念的相关学习

目录 1.1 决策树的概念 1.2 KNN的概念 1.2.1KNN的基本原理 1.2.2 流程&#xff1a; 1.2.3 优缺点 1.3 深度学习 1.4 梯度下降 损失函数 1.5 特征与特征选择 特征选择的目的 1.6 python中dot函数总结 一维数组的点积&#xff1a; 二维数组&#xff08;矩阵&#xff09;的乘法&am…...

Python 之__name__的用法以及解释

文章目录 介绍代码 介绍 __name__ 是一个在 Python 中特殊的内置变量&#xff0c;用于确定一个 Python 文件是被直接运行还是被导入为模块。 文件作为模板导入&#xff0c;则其 __name__属性值被自动设置为模块名 文件作为程序直接运行&#xff0c;则__name__属性属性值被自动设…...

【FPGA零基础学习之旅#12】三线制数码管驱动(74HC595)串行移位寄存器驱动

&#x1f389;欢迎来到FPGA专栏~三线制数码管驱动 ☆* o(≧▽≦)o *☆嗨~我是小夏与酒&#x1f379; ✨博客主页&#xff1a;小夏与酒的博客 &#x1f388;该系列文章专栏&#xff1a;FPGA学习之旅 文章作者技术和水平有限&#xff0c;如果文中出现错误&#xff0c;希望大家能指…...

networkX-03-连通度、全局网络效率、局部网络效率、聚类系数计算

文章目录 1.连通度1.1 检查图是否连通1.2 检查有向图是否为强连通1.3 点连通度、边连通度&#xff1a; 2.网络效率2.1全局效率2.2 局部效率2.2.1 查找子图2.2.3 局部效率源码分析 3.聚类系数&#xff08;Clustering Coefficient&#xff09;3.1 聚类系统源码分析 教程仓库地址&…...

【深入解读Redis系列】Redis系列(五):切片集群详解

首发博客地址 https://blog.zysicyj.top/ 系列文章地址[1] 如果 Redis 内存很大怎么办&#xff1f; 假设一台 32G 内存的服务器部署了一个 Redis&#xff0c;内存占用了 25G&#xff0c;会发生什么&#xff1f; 此时最明显的表现是 Redis 的响应变慢&#xff0c;甚至非常慢。 这…...

无涯教程-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请求提交数据呢&#xff1f; 设置请求头必须在open之后,send之前 请求头里的设置好比…...

产品团队的需求分析指南

需求分析是软件开发流程中需求识别与管理的关键环节&#xff0c;需求分析的目的在于确保所有产品需求准确地代表了利益相关者的需求和要求。选择合适的需求分析方式可以帮助我们获取准确的产品需求&#xff0c;从而保证我们所交付的成果与利益相关者预期相符。 一、什么是需求…...

Python算法——排序算法(冒泡、选择、插入、快速、堆排序、并归排序、希尔、计数、桶排序、基数排序)

本文章只展示代码实现 &#xff0c;原理大家可以参考&#xff1a; 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合成&#xff0c;打开窗口 1. 3、右键空白处&#xff0c;新建合成&#xff0c;默认名称为 0010_comp&#xff1b;再右键新建的 0010_comp&#xff0c;新建图层元素 CGLayer层&#xff0c;默…...

深入探讨Java虚拟机(JVM):执行流程、内存管理和垃圾回收机制

目录 什么是JVM&#xff1f; JVM 执行流程 JVM 运行时数据区 堆&#xff08;线程共享&#xff09; Java虚拟机栈&#xff08;线程私有&#xff09; 什么是线程私有? 程序计数器&#xff08;线程私有&#xff09; 方法区&#xff08;线程共享&#xff09; JDK 1.8 元空…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...