LC-2316. 统计无向图中无法互相到达点对数(DFS、并查集)

2023-10-21 10:04

本文主要是介绍LC-2316. 统计无向图中无法互相到达点对数(DFS、并查集),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

中等

给你一个整数 n ,表示一张 无向图 中有 n 个节点,编号为 0n - 1 。同时给你一个二维整数数组 edges ,其中 edges[i] = [ai, bi] 表示节点 aibi 之间有一条 无向 边。

请你返回 无法互相到达 的不同 点对数目

示例 1:

在这里插入图片描述

输入:n = 3, edges = [[0,1],[0,2],[1,2]]
输出:0
解释:所有点都能互相到达,意味着没有点对无法互相到达,所以我们返回 0 。

示例 2:

img

输入:n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出:14
解释:总共有 14 个点对互相无法到达:
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。

提示:

  • 1 <= n <= 105
  • 0 <= edges.length <= 2 * 105
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • 不会有重复边。

DFS

class Solution {// 统计联通分量 个数 和 大小// 然后递推,求出点对个数// 例如 4 1 2// 4 * 1 + 5 * 2public long countPairs(int n, int[][] edges) {List<Integer>[] g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());for(int[] e : edges){int x = e[0], y = e[1];g[x].add(y);g[y].add(x);}boolean[] vis = new boolean[n];List<Integer> list = new ArrayList<>();for(int i = 0; i < n; i++){if(!vis[i]){int cnt = dfs(i, -1, g, vis);list.add(cnt);}}long res = 0l, sum = 0l;for(Integer e : list){res += e * sum;sum += e;}return res;}private int dfs(int x, int fa, List<Integer>[] g, boolean[] vis){int res = 1;vis[x] = true;for(int y : g[x]){if(y != fa && !vis[y])res += dfs(y, x, g, vis);}return res;}
}

并查集

统计连通块大小可以用并查集做

class Solution {// 统计联通分量 个数 和 大小public long countPairs(int n, int[][] edges) {UF uf = new UF(n);for(int[] e : edges){uf.union(Math.max(e[0], e[1]), Math.min(e[0], e[1]));}Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < n; i++){map.merge(uf.find(i), 1, Integer::sum);}long res = 0l, sum = 0l;for(int x : map.keySet()){res += (long)map.get(x) * sum;sum += map.get(x);}return res;}
}/* ------------ 并查集模版 ------------ */
class UF {int[] parent; // par数组用来存储根节点,par[x]=y表示x的根节点为yint[] size; // size[i]表示以i为根的联通块大小int count; // count表示连通块个数,每次调用union时count-1public UF(int n) {this.count = n;parent = new int[n];size = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;size[i] = 1;}}public void union(int x, int y) {int rootx = find(x);int rooty = find(y);if (rootx == rooty) return;else//不是同一个根,即不在同一个集合,就合并parent[rootx] = rooty;size[rooty] += size[rootx];count--;}public int find(int x) {// 路径压缩if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}
}

这篇关于LC-2316. 统计无向图中无法互相到达点对数(DFS、并查集)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/253662

相关文章

SQL Server配置管理器无法打开的四种解决方法

《SQLServer配置管理器无法打开的四种解决方法》本文总结了SQLServer配置管理器无法打开的四种解决方法,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录方法一:桌面图标进入方法二:运行窗口进入检查版本号对照表php方法三:查找文件路径方法四:检查 S

在Linux终端中统计非二进制文件行数的实现方法

《在Linux终端中统计非二进制文件行数的实现方法》在Linux系统中,有时需要统计非二进制文件(如CSV、TXT文件)的行数,而不希望手动打开文件进行查看,例如,在处理大型日志文件、数据文件时,了解... 目录在linux终端中统计非二进制文件的行数技术背景实现步骤1. 使用wc命令2. 使用grep命令

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

Oracle修改端口号之后无法启动的解决方案

《Oracle修改端口号之后无法启动的解决方案》Oracle数据库更改端口后出现监听器无法启动的问题确实较为常见,但并非必然发生,这一问题通常源于​​配置错误或环境冲突​​,而非端口修改本身,以下是系... 目录一、问题根源分析​​​二、保姆级解决方案​​​​步骤1:修正监听器配置文件 (listener.

MySQL版本问题导致项目无法启动问题的解决方案

《MySQL版本问题导致项目无法启动问题的解决方案》本文记录了一次因MySQL版本不一致导致项目启动失败的经历,详细解析了连接错误的原因,并提供了两种解决方案:调整连接字符串禁用SSL或统一MySQL... 目录本地项目启动报错报错原因:解决方案第一个:第二种:容器启动mysql的坑两种修改时区的方法:本地

VS配置好Qt环境之后但无法打开ui界面的问题解决

《VS配置好Qt环境之后但无法打开ui界面的问题解决》本文主要介绍了VS配置好Qt环境之后但无法打开ui界面的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要... 目UKeLvb录找到Qt安装目录中designer.UKeLvBexe的路径找到vs中的解决方案资源

详解如何使用Python从零开始构建文本统计模型

《详解如何使用Python从零开始构建文本统计模型》在自然语言处理领域,词汇表构建是文本预处理的关键环节,本文通过Python代码实践,演示如何从原始文本中提取多尺度特征,并通过动态调整机制构建更精确... 目录一、项目背景与核心思想二、核心代码解析1. 数据加载与预处理2. 多尺度字符统计3. 统计结果可

如何解决yum无法安装epel-release的问题

《如何解决yum无法安装epel-release的问题》:本文主要介绍如何解决yum无法安装epel-release的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录yum无法安装epel-release尝试了第一种方法第二种方法(我就是用这种方法解决的)总结yum

IDEA下"File is read-only"可能原因分析及"找不到或无法加载主类"的问题

《IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题》:本文主要介绍IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题,具有很好的参... 目录1.File is read-only”可能原因2.“找不到或无法加载主类”问题的解决总结1.File

宝塔安装的MySQL无法连接的情况及解决方案

《宝塔安装的MySQL无法连接的情况及解决方案》宝塔面板是一款流行的服务器管理工具,其中集成的MySQL数据库有时会出现连接问题,本文详细介绍两种最常见的MySQL连接错误:“1130-Hostisn... 目录一、错误 1130:Host ‘xxx.xxx.xxx.xxx’ is not allowed