当前位置:网站首页>Leetcode daily questions (2316. count unreachable pairs of nodes in an undirected graph)
Leetcode daily questions (2316. count unreachable pairs of nodes in an undirected graph)
2022-07-07 09:14:00 【wangjun861205】
You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
Return the number of pairs of different nodes that are unreachable from each other.
Example 1:
Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0
Explanation: There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.
Example 2:
Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14
Explanation: There are 14 pairs of nodes that are unreachable from each other:
[[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]].
Therefore, we return 14.
Constraints:
- 1 <= n <= 105
- 0 <= edges.length <= 2 * 105
- edges[i].length == 2
- 0 <= ai, bi < n
- ai != bi
- There are no repeated edges.
use union-find To turn every isolated graph into a tree , Then we can get the number of nodes in each tree , hypothesis nodes[i] Is the number of nodes in the current tree , that n - nodes[i] Is the number of nodes that are not connected to the nodes in the current tree , nodes[i] * (n - nodes[i]) Namely pair The number of , Traverse all the numbers to calculate pair The final answer is to add up the quantity
use std::collections::HashMap;
impl Solution {
fn find(parent: &mut Vec<i32>, n: i32) -> i32 {
let mut p = parent[n as usize];
if p == n {
return p;
}
p = Solution::find(parent, p);
parent[n as usize] = p;
p
}
fn union(parent: &mut Vec<i32>, a: i32, b: i32) {
let pa = Solution::find(parent, a);
let pb = Solution::find(parent, b);
parent[pa as usize] = pb;
}
pub fn count_pairs(n: i32, edges: Vec<Vec<i32>>) -> i64 {
let mut parent: Vec<i32> = (0..n).collect();
for e in edges {
Solution::union(&mut parent, e[0], e[1]);
}
while {
let mut modified = false;
for i in 0..n as usize {
let pp = parent[parent[i] as usize];
if parent[i] != pp {
Solution::union(&mut parent, i as i32, pp);
modified = true;
}
}
modified
} {
}
let m = parent.into_iter().fold(HashMap::new(), |mut m, v| {
*m.entry(v).or_insert(0) += 1;
m
});
let mut ans = 0;
for v in m.values() {
ans += *v * (n as i64 - *v);
}
ans / 2
}
}
边栏推荐
- 硬件大熊原创合集(2022/06更新)
- PMP certificate preparation experience sharing
- 硬件大熊原创合集(2022/05更新)
- Original collection of hardware bear (updated on June 2022)
- C语言指针(下篇)
- go mod module declares its path as: gtihub. com/xxx-xx but was required as:xx-xx
- How does the project manager write the weekly summary and weekly plan?
- Simulation volume leetcode [general] 1557 The minimum number of points that can reach all points
- OpenGL 3D graphics rendering
- C language pointer (Part 2)
猜你喜欢
Goldbach conjecture C language
Two schemes of unit test
Serial port experiment - simple data sending and receiving
【istio简介、架构、组件】
Locust performance test 3 (high concurrency, parameter correlation, assembly point)
串口實驗——簡單數據收發
Druid monitoring - Introduction to JMX usage and principle
PMP Exam details after the release of the new exam outline
C语言指针(特别篇)
MySQL master-slave delay solution
随机推荐
寄存器地址名映射
Screen automatically generates database documents
Unityshader introduction essentials personal summary -- Basic chapter (I)
MySql数据库-索引-学习笔记
Calf problem
Goldbach conjecture C language
OpenGL三维图形绘制
External interrupt to realize key experiment
面试题:高速PCB一般布局、布线原则
Original collection of hardware bear (updated on May 2022)
STM32 clock system
Several common database connection methods
Locust performance test 2 (interface request)
What is the use of PMP certificate?
模拟卷Leetcode【普通】1609. 奇偶树
Interpretation of MySQL optimization principle
Leetcode question brushing record (array) combination sum, combination sum II
PMP Exam Preparation experience systematically improve project management knowledge through learning
Unity Shader入门精要初级篇(一)-- 基础光照笔记
Ppt template and material download website (pure dry goods, recommended Collection)