【算法题】1761. 一个图中连通三元组的最小度数

题目:

给你一个无向图,整数 n 表示图中节点的数目,edges 数组表示图中的边,其中 edges[i] = [ui, vi] ,表示 ui 和 vi 之间有一条无向边。

一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。

连通三元组的度数 是所有满足此条件的边的数目:一个顶点在这个三元组内,而另一个顶点不在这个三元组内。

请你返回所有连通三元组中度数的 最小值 ,如果图中没有连通三元组,那么返回 -1 。

示例1:
image.png

输入:n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
输出:3
解释:只有一个三元组 [1,2,3] 。构成度数的边在上图中已被加粗。

示例 2:
image.png
输入:n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
输出:0
解释:有 3 个三元组:

  1. [1,4,3],度数为 0 。
  2. [2,5,6],度数为 2 。
  3. [5,6,7],度数为 2 。

提示:

2 <= n <= 400
edges[i].length == 2
1 <= edges.length <= n * (n-1) / 2
1 <= ui, vi <= n
ui != vi
图中没有重复的边。

java代码:

class Solution {public int minTrioDegree(int n, int[][] edges) {int[][] g = new int[n][n];int[] degree = new int[n];for (int[] edge : edges) {int x = edge[0] - 1, y = edge[1] - 1;g[x][y] = g[y][x] = 1;++degree[x];++degree[y];}int ans = Integer.MAX_VALUE;for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {if (g[i][j] == 1) {for (int k = j + 1; k < n; ++k) {if (g[i][k] == 1 && g[j][k] == 1) {ans = Math.min(ans, degree[i] + degree[j] + degree[k] - 6);}}}}}return ans == Integer.MAX_VALUE ? -1 : ans;}
}

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

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

相关文章

恢复数据的利器:易我数据恢复终身技术版v16.2.0.0

EaseUS Data Recovery Wizard为全球提供数据恢复方案,用于误删数据数据,电脑误删文件恢复,格式化硬盘数据恢复,手机U盘数据恢复等,RAID磁盘阵列数据恢复,分区丢失及其它未知原因丢失的数据恢复,简单易用轻松的搞定数据恢复。 特点描述 - 易我数据恢复中文便携版&#xff0c;无…

Kitchen Hook

双扛厨房排钩&#xff1a;挂刀具

HuggingFace 简介

HuggingFace 简介 0. HuggingFace 简介1. HuggingFace 官网地址2. HuggingFace 标准研发流程3. HuggingFace 工具集4. 编码工具4.1 编码工具介绍4.2 使用编码工具 5. 数据集工具5.1 数据集工具介绍5.2 使用数据集工具 6. 评价指标工具6.1 评价指标工具介绍6.2 使用评价指标工具…

vmware 16增加硬盘容量并在Ubuntu 18.04上边格式化并挂载

参考了《增加 VM虚拟机硬盘容量》 《Linux学习之分区挂载》中有给VMWare 16虚拟机添加一块硬盘的内容&#xff0c;需要先参考添加硬盘。 sudo mkfs.ext4 /dev/sda4给/dev/sda4进行ext4格式化。 sudo mkdir /mountsda4新建一个挂载目录。 sudo mount -t ext4 /dev/sda4 /mo…

gitlab升级

1.下载需要的版本 wget -c https://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el7/gitlab-ce-15.7.6-ce.0.el7.x86_64.rpm --no-check-certificate gitlab-ce-15.4.6-ce.0.el7.x86_64.rpm gitlab-ce-15.7.6-ce.0.el7.x86_64.rpm gitlab-ce-15.9.7-ce.0.el7.x86_64.rpm g…

可扩展的Blender插件开发汇总

成熟的 Blender 3D 插件是令人惊奇的事情。作为 Python 和 Blender 的新手,我经常发现自己被社区中的人们创造的强大的东西弄得目瞪口呆。坦率地说,其中一些包看起来有点神奇,当自我怀疑或冒名顶替综合症的唠叨声音被打破时,很容易想到“如果有人能做出可以做xxx的东西就好…

JS踩坑: for let 和 for var的区别

最近踩了一个js的坑 踩坑代码 如下两段代码&#xff0c;看起来没什么区别&#xff0c;但是实际运行效果却不一样 for (let i 0; i < 10; i) {console.log("for:" i);setTimeout(() > {console.log("setTimeout:" i);}, 1000); }输出&#xff1…

openGauss学习笔记-55 openGauss 高级特性-全密态数据库

文章目录 openGauss学习笔记-55 openGauss 高级特性-全密态数据库55.1 连接全密态数据库55.2 创建用户密钥55.3 创建加密表55.4 向加密表插入数据并进行查询 openGauss学习笔记-55 openGauss 高级特性-全密态数据库 全密态数据库意在解决数据全生命周期的隐私保护问题&#xf…

git学习笔记 | 版本管理 - 分支管理

文章目录 git学习笔记Git是什么仓库常见的命令commit 备注规范在文件下设置git忽略文件 .gitignore 版本管理git log | git reflog 查看提交日志/历史版本版本穿梭 git resetgit reset HEAD <file> git checkout -- fileName 丢弃工作区的修改git revertGit恢复之前版本的…

裸露土方智能识别算法 python

裸露土方智能识别算法通过opencvpython网络模型框架算法&#xff0c;裸露土方智能识别算法能够准确识别现场土堆的裸露情况&#xff0c;并对超过40%部分裸露的土堆进行抓拍预警。此次算法用到的Python是一种由Guido van Rossum开发的通用编程语言&#xff0c;它很快就变得非常流…

Visual Studio(2022)生成链接过程的.map映射文件以及.map映射文件的内容说明

微软的官方说明 /MAP&#xff08;生成映射文件&#xff09; | Microsoft Learn 设置步骤 1. 右键项目属性, 连接器 -> 常规 -> 启用增量链接&#xff0c;设置为否。如下图&#xff1a; 2. 连接器 -> 调试 生成调试信息 设置为 生成调试信息 (/DEBUG) 生成程序数据库…

风险评估

风险评估概念 风险评估是一种系统性的方法&#xff0c;用于识别、评估和量化潜在的风险和威胁&#xff0c;以便组织或个人能够采取适当的措施来管理和减轻这些风险。 风险评估的目的 风险评估要素关系 技术评估和管理评估 风险评估分析原理 风险评估服务 风险评估实施流程

AutoSAR CP 飞阅TIME

目录 什么是autosar autosar 做了什么 Foundation、CP、AP CLASSIC PLATFORM &#xff08;CP&#xff09; ADAPTIVE PLATFORM 基于autosar 开发 SWC Port Runnables RTE BSW MCAL CDD I/O Hardware Abstraction Communication Hardware Abstraction Memory Har…

C#基础知识点记录

目录 课程一、C#基础1.C#编译环境、基础语法2.Winform-后续未学完 课程二、Timothy C#底层讲解一、类成员0常量1字段2属性3索引器5方法5.1值参数&#xff08;创建副本&#xff0c;方法内对值的操作&#xff0c;不会影响原来变量的值&#xff09;5.2引用参数&#xff08;传的是地…

财务部发布《企业数据资源相关会计处理暂行规定》

导读 财务部为规范企业数据资源相关会计处理&#xff0c;强化相关会计信息披露&#xff0c;根据《中华人民共和国会计法》和相关企业会计准则&#xff0c;制定了《企业数据资源相关会计处理暂行规定》。 加gzh“大数据食铁兽”&#xff0c;回复“20230828”获取材料完整版 来…

【Java核心知识】JUC包相关知识

文章目录 JUC包主要内容Java内置锁为什么会有线程安全问题Synchronize锁Java对象结构Synchronize锁优化线程间通信Synchronize与wait原理 CAS和JUC原子类CAS原理JUC原子类ABA问题 可见性和有序性为什么会有可见性参考链接 显式锁Lock接口常用方法显式锁分类显式锁实现原理参考链…

gitlab-runner安装和部署项目

目录 1.安装gitlab-runner 1.1 添加官方仓库 1.2.1 安装最新版本 1.2.2 安装指定版本&#xff08;可选&#xff09; 1.2.3 更新runner&#xff08;可选&#xff09; 1.3 随便点开gitlab上的一个项目 1.4 gitlab-runner的注册 2.配置gitlab-runner 3.runner一些命令 gi…

Blender界面学习02

学习视频 【基础篇】1.3 认识界面_哔哩哔哩_bilibili 基本的3d建模的流程是什么&#xff1f; 四个角现出加号时可以拆分窗口&#xff0c;也可以合并窗口 向自己的方向拉是合并&#xff0c;向不是自己的方向拉是合并 如果界面搞乱后需要回到原来的布局 然后在新建的布局上右击 …

HTML5+CSS3+JS小实例:科技感满满的鼠标移动推开粒子特效

实例:科技感满满的鼠标移动推开粒子特效 技术栈:HTML+CSS+JS 效果: 源码: 【html】 <!DOCTYPE html> <html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta name="viewport&qu…