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

图中的最短环

2608. 图中的最短环

现有一个含 n 个顶点的 双向 图,每个顶点按从 0n - 1 标记。图中的边由二维整数数组 edges 表示,其中 edges[i] = [ui, vi] 表示顶点 uivi 之间存在一条边。每对顶点最多通过一条边连接,并且不存在与自身相连的顶点。

返回图中 最短 环的长度。如果不存在环,则返回 -1

是指以同一节点开始和结束,并且路径中的每条边仅使用一次。

示例 1:

**输入:**n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
**输出:**3
**解释:**长度最小的循环是:0 -> 1 -> 2 -> 0

示例 2:

**输入:**n = 4, edges = [[0,1],[0,2]]
**输出:**-1
**解释:**图中不存在循环

提示:

  • 2 <= n <= 1000
  • 1 <= edges.length <= 1000
  • edges[i].length == 2
  • 0 <= ui, vi < n
  • ui != vi
  • 不存在重复的边

还是删除边比较容易写

class Solution {
public:int findShortestCycle(int n, vector<vector<int>>& edges) {for (int i = 0; i < 1000; i++) fa[i] = i;vector<pair<int, int>> sto; // 存储环的起始和结束节点for (auto u : edges) {int x = find(u[0]), y = find(u[1]);if (x != y) {fa[x] = y;}else {sto.push_back({ u[0],u[1] });}e[u[0]].push_back(u[1]);e[u[1]].push_back(u[0]);}if (sto.size() == 0) return -1;int ans = 0xffffff;for (auto [u,v] : sto) {queue<pair<int, int>> q;vector<bool> vis(n + 1, 0);q.push({ u,1 });while (q.size()) {auto [node, step] = q.front(); q.pop();if (node == v) {ans = min(ans, step); break;}if (vis[node]) continue;vis[node] = 1;for (auto to : e[node]) {if (node == u && to == v) continue; // 跳开一条断边q.push({ to,step + 1 });}}}return ans;}int find(int x) {if (x == fa[x]) return x;return fa[x] = find(fa[x]);}int fa[1001];vector<int> e[1001];};

我们再看一个题目,如果权重
在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;const int N = 105;
int e[N][N];
int n,m;
const int M = (int)5e3+5;
int edge[M],ne[M],h[N],idx = 0;
int w[M];
int fa[N];void add(int a,int b,int wei){edge[++idx] = b, ne[idx] = h[a], h[a] = idx;w[idx] = wei;
}int find(int x){if(x==fa[x]) return x;return fa[x] = find(fa[x]);
}int main(){cin >> n >> m;// 开始处理fafor(int i=0;i<=n;i++) fa[i] = i; vector<pair<int,int>> sto;for(int i=1;i<=m;i++){int u,v,d;cin >> u >> v >> d;if(e[u][v]==0){e[u][v] = d;e[v][u] = d;}else{if(e[u][v]>d){e[u][v] = d;e[v][u] = d;}}}	for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){if(e[i][j]){int x = find(i), y = find(j);if(x!=y) fa[x] = y;else {sto.push_back({i,j});}add(i,j,e[i][j]);add(j,i,e[i][j]);}}}
//	if(sto.size()==0) {
//		cout << "No solution."; return 0;
//	}int ans = 0x7fffffff;for(auto x:sto){vector<bool> vis(n+1);int u = x.first, v = x.second;priority_queue<pair<int,int>> q;q.push({0,u});while(q.size()){int d = -q.top().first, node = q.top().second; q.pop();if(vis[node]) continue;vis[node] = 1;if(node==v){ans = min(ans,d+e[v][u]); break;}for(int i=h[node];i;i=ne[i]){int to = edge[i], ww = w[i];if(node==u&&to==v) continue;q.push({-(d+ww),to});}}}if(ans!=0x7fffffff)cout << ans;else cout << "No solution."; return 0;
}

相关文章:

图中的最短环

2608. 图中的最短环 现有一个含 n 个顶点的 双向 图&#xff0c;每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示&#xff0c;其中 edges[i] [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接&#xff0c;并且不存在与自身相连的顶…...

安装依赖 npm install idealTree:lib: sill idealTree buildDeps 卡着不动

我一直怀疑是网络问题&#xff0c;因为等了很久也能安装成功&#xff0c;就是时间比较长&#xff0c;直到现在完全受不了了&#xff0c;决定好好整治下这个问题&#xff01; 1、执行命令 npm config get userconfig 查看配置文件所在位置&#xff0c;将其删除。 2、执行 n…...

LLMs之Llama 3.1:Llama 3.1的简介、安装和使用方法、案例应用之详细攻略

LLMs之Llama 3.1&#xff1a;Llama 3.1的简介、安装和使用方法、案例应用之详细攻略 导读&#xff1a;2024年7月23日&#xff0c;Meta重磅推出Llama 3.1。本篇文章主要提到了Meta推出的Llama 3.1自然语言生成模型。 背景和痛点 >> 过去开源的大型语言模型在能力和性能上一…...

如何实现一个大模型在回答问题时同时提供相关内容链接

通义生成 为了让大模型在回答问题时能够提供相关内容链接&#xff0c;通常采用的方法是结合检索增强生成&#xff08;Retrieval-Augmented Generation, RAG&#xff09;的技术。这种方法可以让大模型在生成答案的同时&#xff0c;从外部知识源中检索相关信息&#xff0c;并将这…...

<数据集>玉米地杂草识别数据集<目标检测>

数据集格式&#xff1a;VOCYOLO格式 图片数量&#xff1a;9900张 标注数量(xml文件个数)&#xff1a;9900 标注数量(txt文件个数)&#xff1a;9900 标注类别数&#xff1a;2 标注类别名称&#xff1a;[Maize, Weed] 序号类别名称图片数框数1Maize8439125142Weed959231048…...

vue3中动态添加form表单校验

<template><div><div v-for"(formData, index) in forms" :key"index"><u-form :model"formData" :rules"rules" ref"formRefs"><u-form-item label"用户名" prop"username"…...

Java面试八股之什么是声明式事务管理,spring怎么实现声明式事务管理?

什么是声明式事务管理&#xff0c;spring怎么实现声明式事务管理&#xff1f; 声明式事务管理是一种编程范式&#xff0c;它允许开发人员通过声明性的配置或注解&#xff0c;而不是硬编码事务处理逻辑&#xff0c;来指定哪些方法或类应该在其上下文中执行事务。这种方法将事务…...

springboot 缓存预热的几种方案

缓存预热是指在 Spring Boot 项目启动时&#xff0c;预先将数据加载到缓存系统&#xff08;如 Redis&#xff09;中的一种机制。 这里我给大家总结几个缓存预热的方案。 方案1&#xff1a;使用启动监听事件实现缓存预热 可以使用 ApplicationListener 监听 ContextRefreshed…...

谷粒商城实战笔记-62-商品服务-API-品牌管理-OSS整合测试

文章目录 一&#xff0c;Java中上传文件到阿里云OSS1&#xff0c;整合阿里云OSS2&#xff0c;测试上传文件 二&#xff0c;Java中整合阿里云OSS服务指南引言准备工作1. 注册阿里云账号2. 获取Access Key3. 添加依赖 实现OSS客户端1. 初始化OSSClient2. 创建Bucket3. 上传文件4.…...

linux c 递归锁的介绍

递归锁的递归特性确实只是对于持有锁的线程。当一个线程获取了递归锁后&#xff0c;它可以多次重复获取该锁&#xff0c;而不会导致自身阻塞或死锁。这是递归锁的重要特点&#xff0c;它允许同一个线程在已经持有锁的情况下&#xff0c;再次获取相同的锁。 然而&#xff0c;对…...

React好用的组件库有哪些

React好用的组件库有很多&#xff0c;它们各自具有不同的特点和优势&#xff0c;适用于不同的开发场景和需求。以下是一些受欢迎的React组件库及其特点&#xff1a; Material-UI&#xff08;现更名为MUI&#xff09; 特点&#xff1a;这是一个开源的React组件库&#xff0c;实…...

简单快捷!Yarn的安装与使用指南

Yarn 是由 Facebook (现 Meta) 开发的包管理工具。 今天&#xff0c;我将介绍如何使用 Yarn。 目录 Yarn 的官方网站 关于安装 版本确认 开始一个新项目&#xff08;创建 package.json 文件&#xff09; 安装软件包 升级包 运行脚本 执行包的命令 卸载包 总结 Yarn 的…...

【Django】前端技术-网页样式表CSS

文章目录 一、申明规则CSS的导入方式行内样式内部样式外部样式 二、CSS的选择器1. 基本选择器标签选择器&#xff1a; 选择一类标签 标签{}类选择器 class&#xff1a; 选择所有class属性一致的表情&#xff0c;跨标签.类名{}ID选择器&#xff1a;全局唯一 #id名{} 2.层次选择器…...

openssl req 详解

一、openssl req 该命令用于创建和处理PKCS#10格式的证书请求&#xff08;certificate requests CSRs&#xff09;&#xff0c;也可以用来创建自签名证书&#xff08; self-signed certificates&#xff09;来当作根证书&#xff08;root CAs&#xff09;使用 -new 该选项用来…...

mysql各种锁总结

mysql全局锁 读锁&#xff08;共享锁&#xff09; 阻止其他用户更新&#xff0c;但允许他们读取数据。 写锁&#xff08;排他锁&#xff09; 阻止其他用户读取和更新数据。 全局锁场景&#xff1a;进行数据库备份 数据库备份 背景&#xff1a;备份数据肯定要保证数据一致…...

SpringSecurity--DelegatingFilterProxy工作流程

什么是 DelegatingFilterProxy&#xff1f; DelegatingFilterProxy 是 Spring 提供的一个特殊的过滤器&#xff0c;它起到了桥梁的作用&#xff0c;可以让你在 Spring 容器中管理 Servlet 容器中的过滤器。 为什么需要 DelegatingFilterProxy&#xff1f; 通常情况下&#x…...

GitHub每日最火火火项目(7.27)

1. 项目名称&#xff1a;meta - llama / llama3 项目介绍&#xff1a;这是 Meta Llama 3 的官方 GitHub 站点。目前尚不清楚该项目的具体功能和特点&#xff0c;但从名称推测&#xff0c;可能与 Llama 3 模型相关&#xff0c;或许涉及到模型的开发、训练或应用等方面。 项目地…...

git 学习总结

文章目录 一、 git 基础操作1、工作区2、暂存区3、本地仓库4、远程仓库 二、git 的本质三、分支git 命令总结 作者: baron 一、 git 基础操作 如图所示 git 总共有几个区域 工作区, 暂存区, 本地仓库, 远程仓库. 1、工作区 存放项目代码的地方&#xff0c;他有两种状态 Unm…...

《如何找到自己想做的事》

Arouse Enthusiasm, Give Scope to Skill, Explore The Essence *摘其两纸 我喜欢打篮球&#xff0c;并不是我真的喜欢这项运动&#xff0c;而是我喜欢团队竞技。我喜欢看书&#xff0c;并不是我真喜欢阅读&#xff0c;而是我想要了解世界运行逻辑。寻找热爱&#xff0c;探寻本…...

Vue中el的两种写法

大家好我是前端寄术区博主PleaSure乐事。今天了解到了Vue当中有关el的两种写法&#xff0c;记录下来与大家分享&#xff0c;希望对大家有所帮助。 方法一 解释 第一种方法我们直接用new创建并初始化一个新的 Vue 实例&#xff0c;并定义了 Vue 实例的数据对象&#xff0c;在给…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...