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

leetcode 2316.统计无向图中无法互相到达点对数

思路:并查集

其实就是连通块的一个变形题目,一般的连通块题目要我们求的是连通个数,或者能不能到达,这里反过来问了。

首先,我们用dfs也是可以做到的,在dfs中统计每一个连通块的个数,然后用乘法原理相乘,累计相加就得到结果了。

这里并查集思路差不多,只是用了并查集来找连通块而已。(这里并查集多了一个权值,用来统计每个并查集的点的个数)

注意:作者在统计多少对点到达不了的时候不会统计。这里看题解给出了思路,就是对于每一个连通块来说,连通块里面的点和另一个连通块里面的点是互不联通的,所以这里可以用乘法原理相乘,接着,我们再加入累加器当中,然后让点的个数合并成这两个连通块一共的点数,再让下一个连通块乘以这些点数,因为下一个连通块的每一点又与这两个连通块的每一个点都不相通,所以继续这样下去,累加,计数....

上代码:

class Solution {
public:
int f[100020];
int zhi[100020];
int find(int u){if(f[u]==u)return u;elsereturn f[u]=find(f[u]);
}
void unit(int x,int y){int s=find(x);if(find(y)==s)return;else{zhi[find(y)]+=zhi[s];f[s]=find(y);}
}long long countPairs(int n, vector<vector<int>>& edges) {for(int i=0;i<n;i++){f[i]=i;zhi[i]=1;}for(int i=0;i<edges.size();i++){int x=edges[i][0];int y=edges[i][1];unit(x,y);}long long res=0;long long size=0;for(int i=0;i<n;i++){if(f[i]==i){res+=zhi[i]*size;//size+=zhi[i];//需要学习的地方}}return res;}
};

相关文章:

leetcode 2316.统计无向图中无法互相到达点对数

思路&#xff1a;并查集 其实就是连通块的一个变形题目&#xff0c;一般的连通块题目要我们求的是连通个数&#xff0c;或者能不能到达&#xff0c;这里反过来问了。 首先&#xff0c;我们用dfs也是可以做到的&#xff0c;在dfs中统计每一个连通块的个数&#xff0c;然后用乘…...

WPS二次开发系列:如何使用WPS返回的FileUri

作者持续关注 WPS二次开发专题系列&#xff0c;持续为大家带来更多有价值的WPS开发技术细节&#xff0c;如果能够帮助到您&#xff0c;请帮忙来个一键三连&#xff0c;更多问题请联系我&#xff08;QQ:250325397&#xff09; 目录 什么是FileUri 在SDK中的使用场景 打开文档时…...

python删除一个文件夹所有文件

在Python中&#xff0c;可以使用os模块来删除一个文件夹中的所有文件&#xff0c;但保留文件夹本身。以下是一个简单的例子&#xff1a; import osdef delete_files_in_folder(folder_path):for filename in os.listdir(folder_path):file_path os.path.join(folder_path, fi…...

overflow:hidden对解决外边距塌陷的个人理解

外边距塌陷&#xff1a; 子元素的上外边距大于父元素的上外边距&#xff0c;导致边距折叠&#xff0c;取两者之间最大值&#xff0c;即子元素外边距&#xff0c;导致父元素上外边距失效。 解决办法&#xff1a;在父元素样式添加overflow:hidden;或者border:1px solid black;(不…...

【linux软件基础知识】- 文件的概念:Linux 中的文件

Linux 中的文件 在 Linux 中,文件是存储在存储设备(例如硬盘驱动器或固态驱动器)上的数据项的集合。 文件被组织为字节序列,并由文件系统中的唯一名称来标识。 以下是 Linux 中文件的一些关键特征: 字节序列:Linux 中的文件被视为字节序列。 每个字节可以表示一个字符…...

Context capture/Pix4Dmapper/AutoCAD/CASS/EPS软件的安装流程与使用方法;土方量计算;无人机摄影测量数据处理

目录 专题一 无人机摄影测量技术应用现状及其发展 专题二 基本原理和关键技术讲解 专题三 无人机影像外业数据获取 专题四 数据处理环境建立与软件熟悉 专题五 GNSS数据土方量计算 专题六 基于无人机影像数据的正射影像制作 专题七 基于无人机影像数据的三维模型制作 专…...

算法系列之堆排序实践哪家强

1.概念 堆排序是一种树形选择排序&#xff0c;是对简单选择排序的有效改进和优化。 堆(heap)&#xff0c;这里所说的堆是数据结构中的堆&#xff08;对应于算法&#xff09;&#xff0c;而不是内存模型中的堆&#xff08;数据存储形式&#xff0c;还比如&#xff1a;栈&#…...

01-win10安装Qt5

Qt5安装教程 下载Qt5官网下载(下载很慢)镜像网站下载(有些版本没有资源)迅雷下载(推荐)百度网盘下载(推荐)安装Qt5下载Qt5 官网下载(下载很慢) 【注意】:官网下载非常慢,没有镜像下载时常20+ Qt 官网有一个专门的资源下载网站,所有的开发环境和相关工具都可以从这…...

mybatis使用及配置相关,仅做个人记录

在spring-boot项目中mybatis的配置文件在yml文件中&#xff0c;并没有mybatisconfig.xml文件 yml文件中配置&#xff1a;&#xff08;来源&#xff1a;https://blog.51cto.com/u_16213723/8747999&#xff09; mybatis:# XML文件路径&#xff0c;可配置多个&#xff0c;逗号分…...

【STM32 |新建一个工程】基于标准库(库函数)新建工程

目录 STM32开发方式 库函数文件夹 建工程步骤 库函数工程建立 建立工程总结 STM32开发方式 目前stm32的开发方式主要有基于寄存器的方式、基于标准库的方式&#xff08;库函数的方式&#xff09;、基于HAL库的方式基于库函数的方式是使用ST官方提供的封装好的函数&…...

C#利用ClearScript执行Javascript脚本

1&#xff0c;新建.netframework winform工程 2&#xff0c;打开nuget程序包管理界面&#xff0c;安装Microsoft.ClearScript.V8&#xff0c;Microsoft.ClearScript.V8.Native.win-x64. 3,编写Javascript脚本,另存为demo.js function testFunc(t) {return t "&#xf…...

住宅ip与数据中心ip代理的区别是什么

代理通常意味着“替代”。它是用户设备和目标服务器之间的中介&#xff0c;允许在不同的IP地址下上网。代理ip根据来源分类可分住宅ip与数据中心ip&#xff0c;二者之间区别是什么呢&#xff1f; 住宅ip是由互联网服务提供商(ISP)提供给家庭的IP地址。出于这个原因&#xff0c…...

【计算机网络】数据链路层的功能

数据链路层的基本功能&#xff1a; 封装成帧透明传输差错检测 数据链路层使用的信道主要有两种 点对点信道——PPP协议广播信道——CSMA/CD协议(有线局域网)、CSMA/CA协议(无线局域网) 数据链路层所处的地位 从图中可以看出&#xff0c;数据从主机H1送到主机H2需要在路径中…...

信号线电路串联电阻

简介 两芯片端串联一个电阻&#xff0c;在靠近发送端或接收端。 一般串联的是0Ω, 22Ω, 33Ω的电阻&#xff0c;也可能更大。 目的 1.解决信号反射问题&#xff0c;吸收反射。 问题如下&#xff1a; pcb单端阻抗过大&#xff0c;而接收端是cmos输入&#xff0c;使得接收端…...

手机App防沉迷系统-算法

import java.util.*; public class Main{public static void main(String[] args){Scanner innew Scanner(System.in);int nInteger.parseInt(in.nextLine());//已注册app列表List<Log> listnew ArrayList<>();for(int k0;k<n;k){String[] strin.nextLine().spl…...

day3_prefixSum

一、前缀和技巧 重点 前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和 个人理解&#xff1b;预计算&#xff0c;空间换时间 1.(一维数组的前缀和)303区域和检索-数组不可变 获取闭区间值 [left,right] -> preSum[right 1] - preSum[left],其中preSum[right…...

Redis过期删除策略和内存淘汰策略有什么区别?

Redis过期删除策略和内存淘汰策略有什么区别&#xff1f; 前言过期删除策略如何设置过期时间&#xff1f;如何判定 key 已过期了&#xff1f;过期删除策略有哪些&#xff1f;Redis 过期删除策略是什么&#xff1f; 内存淘汰策略如何设置 Redis 最大运行内存&#xff1f;Redis 内…...

【计算机网络】物理层传输介质 习题3

双绞线是用两根绝缘导线绞合而成的&#xff0c;绞合的目的是( )。 A.减少干扰 B.提高传输速度 C.增大传输距离 D.增大抗拉强度 在电缆中采用屏蔽技术带来的好处主要是( ) A.减少信号衰减 B. 减少电磁干扰辐射 C.减少物理损坏 D. 减少电缆的阻抗 利用一根同轴电缆互连主机构成…...

智能座舱语音助手产品方案

一、用户调研与痛点分析 1.目标用户分析 用户画像 性别女性年龄50地域2-3线城市职业退休或退居二线教育中专、 大专、 本科财务家庭财务管理者爱好享受生活、 照顾家庭标签有闲有小钱二、产品定位与卖点提炼 购车目的 愉悦自我&#xff0c; 专属于自己的座驾&#xff1a; 家…...

经典面试题之滑动窗口专题

class Solution { public:int minSubArrayLen(int target, vector<int>& nums) {// 长度最小的子数组 // 大于等于 targetint min_len INT32_MAX;// 总和int sum 0;int start 0; // 起点for(int i 0; i< nums.size(); i) {sum nums[i];while(sum > targe…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...