【力扣每日一题】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;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/117083.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Windows下Redis的安装

文章目录 一,Redis介绍二,Redis下载三,Redis安装-解压四,Redis配置五,Redis启动和关闭(通过terminal操作)六,Redis连接七,Redis使用 一,Redis介绍 远程字典服务,一个开源的,键值对形式的在线服务框架,值支持多数据结构,本文介绍windows下Redis的安装,配置相关,官网默认下载的是…

QT day1

作业&#xff1a; 编写一个类似图片的 #include "burger.h"burger::burger(QWidget *parent): QWidget(parent) {//设置初始尺寸this->resize(400,320);//设置尺寸最大值最小值this->setMaximumSize(400,320);this->setMinimumSize(400,320);//设置窗口标…

中国行政区域带坐标经纬度sql文件及地点获取经纬度方法

文章目录 前言一、如何获取某地的经纬度&#xff1f;1.1 搜索百度地图1.2 在下方找到地图开放平台1.3 下滑找到坐标拾取器1.4 使用 二、sql文件2.1 创建表2.2 插入数据 前言 当工作业务上需要涉及地图&#xff0c;给前端返回经纬度等场景&#xff0c;需要掌握区域经纬度的获取…

在iPhone 15发布之前,iPhone在智能手机出货量上占据主导地位,这对安卓来说是个坏消息

可以说这是一记重拳&#xff0c;但似乎没有一个有价值的竞争者能与苹果今年迄今为止的智能手机出货量相媲美。 事实上&#xff0c;根据Omdia智能手机型号市场跟踪机构收集的数据&#xff0c;苹果的iPhone占据了前四名。位居榜首的是iPhone 14 Pro Max&#xff0c;2023年上半年…

C# Linq源码分析之Take(四)

概要 本文主要对Take的优化方法进行源码分析&#xff0c;分析Take在配合Select&#xff0c;Where等常用的Linq扩展方法使用时候&#xff0c;如何实现优化处理。 本文涉及到Select, Where和Take和三个方法的源码分析&#xff0c;其中Select, Where, Take更详尽的源码分析&…

iOS开发Swift-3-UI与按钮Button-摇骰子App

1.创建新项目Dice 2.图标 删去AppIcon&#xff0c;将解压后的AppIcon.appiconset文件拖入Assets包。 3.将素材点数1-6通过网页制作成2x&#xff0c;3x版本并拖入Asset。 4.设置对应的UI。 5.拖入Button组件并设置style。 6.Ctrl加拖拽将Button拖拽到ViewController里&#xff0…

WPF实战项目十三(API篇):备忘录功能api接口、优化待办事项api接口

1、新建MenoDto.cs /// <summary>/// 备忘录传输实体/// </summary>public class MemoDto : BaseDto{private string title;/// <summary>/// 标题/// </summary>public string Title{get { return title; }set { title value; OnPropertyChanged();…

Day5:react函数组件与类组件

「目标」: 持续输出&#xff01;每日分享关于web前端常见知识、面试题、性能优化、新技术等方面的内容。 「主要面向群体&#xff1a;」前端开发工程师&#xff08;初、中、高级&#xff09;、应届、转行、培训、自学等同学 Day4-今日话题 react「函数组件和类组件」的区别&…

ZLMediaKit 重建docker包

1.下载容器到本地服务器并运行 #此镜像为github持续集成自动编译推送&#xff0c;跟代码(master分支)保持最新状态 docker run -id -p 1935:1935 -p 8080:80 -p 8443:443 -p 8554:554 -p 10000:10000 -p 10000:10000/udp -p 8000:8000/udp -p 9000:9000/udp zlmediakit/zlmedi…

好马配好鞍:Linux Kernel 4.12 正式发布

Linus Torvalds 在内核邮件列表上宣布释出 Linux 4.12&#xff0c;Linux 4.12 的主要特性包括&#xff1a; BFQ 和 Kyber block I/O 调度器&#xff0c;livepatch 改用混合一致性模型&#xff0c;信任的执行环境框架&#xff0c;epoll 加入 busy poll 支持等等&#xff0c;其它…

shell脚本中时间的编写规范20230902

背景&#xff1a;经常写shell&#xff0c;但是很多种时间格式规范真是记不住哈&#xff0c;&#x1f604;&#xff0c;索性记录一下 一、 获取-年 下面的这两种写法都成 year$(date "%Y") yeardate "%Y"echo -e "测试输出 年: ${year}"输出结…

unity 之参数类型之引用类型

文章目录 引用类型引用类型与值类型的差异 引用类型 在Unity中&#xff0c;引用类型是指那些在内存中存储对象引用的数据类型。以下是在Unity中常见的引用类型的介绍&#xff1a; 节点&#xff08;GameObject&#xff09;&#xff1a; 在Unity中&#xff0c;游戏对象&#xff…

DevEco Studio 配置

首先,打开deveco studio 进入首页 …我知道你们想说什么,我也想说 汉化配置 没办法,老样子,先汉化吧,毕竟母语看起来舒服 首先,点击软件左下角的configure,在配置菜单里选择plugins 进入到插件页面, 输入chinese,找到汉化插件,(有一说一写到这我心里真是很不舒服) 然后点击o…

Nmap 7.94 发布:新功能!

Nmap 的最新版本 7.94 在其 26 岁生日之际发布。 最重要的升级是在所有平台上将 Zenmap 和 Ndiff 从 Python 2 迁移到 Python 3。 这个新版本的 Nmap 7.94 进行了升级&#xff0c;进行了多项改进&#xff0c;修复了一些关键错误&#xff0c;并添加了新的 Npcap、操作系统指纹…

浅析Linux系统I/O模型

文章目录 概述阻塞式I/O模型非阻塞式I/O模型I/O多路复用模型信号驱动式I/O模型异步I/O模型相关参考 概述 在操作系统中&#xff0c;I/O类操作是相对慢速的&#xff0c;应用发起一个I/O操作&#xff0c;需要等待I/O资源就绪后&#xff0c;才能继续后面的处理。这种简单的请求-响…

【八股】2023秋招八股复习笔记5(计算机网络-CN)

文章目录 八股目录目录1、应用层 & HTTP一些http题HTTPS 加密原理&#xff08;问过&#xff09;HTTP/1.1 新特性HTTP/2.0 与 RPC&#xff08;问过&#xff09;GET 和 POST 比较 2、传输层 & TCPTCP三次握手 & 四次挥手&#xff08;问过&#xff09;为什么每次TCP 连…

一百六十八、Kettle——用海豚调度器定时调度从Kafka到HDFS的任务脚本(持续更新追踪、持续完善)

一、目的 在实际项目中&#xff0c;从Kafka到HDFS的数据是每天自动生成一个文件&#xff0c;按日期区分。而且Kafka在不断生产数据&#xff0c;因此看看kettle是不是需要时刻运行&#xff1f;能不能按照每日自动生成数据文件&#xff1f; 为了测试实际项目中的海豚定时调度从…

Qt使用Json

包含目录&#xff1a; #include <QJsonObject> #include <QJsonDocument> #include <QByteArray> #include <QFile> #include <QJsonArray>基本结构&#xff1a; 写json QJsonObject studentobj;QJsonArray arrarydata;QJsonObject subdata;…

Android 手游聚合SDK小知识(一)

Android 手游聚合SDK小知识(一) Android 手游聚合SDK小知识(二) 聚合分包 前言 回头想想&#xff0c;在安卓游戏SDK这个领域&#xff0c;我也呆了4年了&#xff0c;从啥都不懂的小菜鸟&#xff0c;逐渐靠自己不断学习&#xff0c;对这个行业也算有了一些理解&#xff0c;趁着…

【Terraform学习】使用 Terraform创建Lambda函数启动EC2(Terraform-AWS最佳实战学习)

本站以分享各种运维经验和运维所需要的技能为主 《python》&#xff1a;python零基础入门学习 《shell》&#xff1a;shell学习 《terraform》持续更新中&#xff1a;terraform_Aws学习零基础入门到最佳实战 《k8》暂未更新 《docker学习》暂未更新 《ceph学习》ceph日常问题解…