当前位置:网站首页>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
}
}
边栏推荐
- Detailed learning notes of JVM memory structure (I)
- Personal deduction topic classification record
- External interrupt to realize key experiment
- Pytest+request+allure+excel interface automatic construction from 0 to 1 [familiar with framework structure]
- Summary of PMP learning materials
- Locust performance test 2 (interface request)
- C语言指针(中篇)
- C language pointer (Part 2)
- The essence of high availability
- Regularly modify the system time of the computer
猜你喜欢
Screen automatically generates database documents
What are the conditions for applying for NPDP?
NVIC中断优先级管理
E-commerce campaign Guide
ESP32-ULP协处理器低功耗模式RTC GPIO中断唤醒
Hard core sharing: a common toolkit for hardware engineers
LeetCode 715. Range module
On December 8th, 2020, the memory of marketing MRC application suddenly increased, resulting in system oom
【istio简介、架构、组件】
Simple use of Xray
随机推荐
Storage of data in memory
OpenGL 3D graphics rendering
On December 8th, 2020, the memory of marketing MRC application suddenly increased, resulting in system oom
Output all composite numbers between 6 and 1000
Troublesome problem of image resizing when using typora to edit markdown to upload CSDN
cmake命令行使用
When inputting an expression in the input box, an error is reported: incorrect string value:'\xf0\x9f... ' for column 'XXX' at row 1
串口實驗——簡單數據收發
C语言指针(习题篇)
Cmake command line use
Idea development environment installation
Leetcode刷题记录(数组)组合总和、组合总和 II
RuntimeError: Calculated padded input size per channel: (1 x 1). Kernel size: (5 x 5). Kernel size c
硬件大熊原创合集(2022/05更新)
Personal deduction topic classification record
【ChaosBlade:节点 CPU 负载、节点网络延迟、节点网络丢包、节点域名访问异常】
2022-06-30 Unity核心8——模型导入
C language pointer (Part 2)
Digital triangle model acwing 1027 Grid access
[istio introduction, architecture, components]