当前位置:网站首页>LeetCode每日一题(2316. Count Unreachable Pairs of Nodes in an Undirected Graph)
LeetCode每日一题(2316. Count Unreachable Pairs of Nodes in an Undirected Graph)
2022-07-07 06:28: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.
用 union-find 的方法来把每一个孤立的图变成一棵树, 然后我们可以得到每棵树里面的节点数量, 假设 nodes[i]是当前树的节点数量, 那 n - nodes[i]就是所有与当前树里的节点不相连的节点数量, nodes[i] * (n - nodes[i])就是 pair 的数量, 遍历所有的数计算出 pair 数量进行加和就是最终答案
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
}
}
边栏推荐
- 【Istio Network CRD VirtualService、Envoyfilter】
- STM32串口寄存器库函数配置方法
- Implement custom memory allocator
- C language pointer (special article)
- Pytest+request+allure+excel interface automatic construction from 0 to 1 [five nails / flying Book notice]
- The longest ascending subsequence model acwing 1017 Strange thief Kidd's glider
- Register address name mapping
- Original collection of hardware bear (updated on June 2022)
- Locust performance test 5 (analysis)
- Led analog and digital dimming
猜你喜欢
2022-07-06 Unity核心9——3D动画
Synchronized underlying principle, volatile keyword analysis
Hard core sharing: a common toolkit for hardware engineers
Locust performance test 2 (interface request)
The essence of high availability
2021 year end summary
UnityShader入门精要个人总结--基础篇(一)
ESP32-ULP协处理器低功耗模式RTC GPIO中断唤醒
H3C vxlan configuration
Esp32-ulp coprocessor low power mode RTC GPIO interrupt wake up
随机推荐
2020 year end summary
Reading notes of pyramid principle
Unity shader beginner's Essentials (I) -- basic lighting notes
Output all composite numbers between 6 and 1000
硬件大熊原创合集(2022/05更新)
Register address name mapping
The essence of high availability
Count the number of words in the string c language
2022-07-06 Unity核心9——3D动画
go mod module declares its path as: gtihub. com/xxx-xx but was required as:xx-xx
Simulation volume leetcode [general] 1705 The maximum number of apples to eat
面试题:高速PCB一般布局、布线原则
C language pointer (special article)
Serial port experiment - simple data sending and receiving
Several common database connection methods
C language pointer (exercises)
Idea development environment installation
Locust performance test 5 (analysis)
端口复用和重映像
Regularly modify the system time of the computer