统计无向图中无法互相到达点对数
难度:
标签:
题目描述
给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
请你返回 无法互相到达 的不同 点对数目 。
示例 1：
输入：n = 3, edges = [[0,1],[0,2],[1,2]] 输出：0 解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。
示例 2：
输入：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 <= 1050 <= edges.length <= 2 * 105edges[i].length == 20 <= ai, bi < nai != bi- 不会有重复边。
代码结果
运行时间: 220 ms, 内存: 62.9 MB
// Java solution using Java Streams to find the number of unreachable pairs
// The idea is to use DSU to find all connected components and then calculate the number of unreachable pairs
import java.util.*;
import java.util.stream.*;
class Solution {
public int countUnreachablePairs(int n, int[][] edges) {
int[] parent = IntStream.range(0, n).toArray();
int[] size = new int[n];
Arrays.fill(size, 1);
// Find the root of a node
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
// Union two sets
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (size[rootX] < size[rootY]) {
int temp = rootX;
rootX = rootY;
rootY = temp;
}
parent[rootY] = rootX;
size[rootX] += size[rootY];
}
}
// Process all edges
Arrays.stream(edges).forEach(edge -> union(edge[0], edge[1]));
// Calculate sizes of all components
Map<Integer, Integer> componentSizes = IntStream.range(0, n)
.mapToObj(i -> find(i))
.collect(Collectors.groupingBy(i -> i, Collectors.summingInt(i -> 1)));
// Calculate the number of unreachable pairs
long totalPairs = (long) n * (n - 1) / 2;
long reachablePairs = componentSizes.values().stream()
.mapToLong(size -> (long) size * (size - 1) / 2)
.sum();
return (int) (totalPairs - reachablePairs);
}
}
解释
方法:
题解使用并查集（Union-Find）来处理图中的连通性问题。首先，每个节点初始化为自己的父节点，通过并查集的union和find操作，将每个边连接的两个节点合并到同一个集合。find操作实现了路径压缩，使得重复查找效率更高。union操作中，将一个集合的根节点指向另一个，同时更新根节点的rank（集合大小）。最后，计算所有不连通的节点对。具体地，首先找出所有的根节点，每个根节点代表一个连通分量。计算每个连通分量的节点数，然后对于每个连通分量，用其节点数乘以剩余所有节点的总数（减去当前连通分量的节点数），得到与当前连通分量中的每个节点不连通的节点对数。最后，为避免重复计算，将结果除以2。
时间复杂度:
O(m + n)
空间复杂度:
O(n)
代码细节讲解
🦆
并查集中的`rank`数组通常用来表示树的高度，为什么在这里它表示连通分量的大小？
▷🦆
在并查集的`union`操作中，为什么选择将`rootX`的父节点设置为`rootY`而不是反过来？是否考虑了树的平衡性？
▷🦆
题解中提到避免重复计算，为什么最后的结果需要除以2？具体是哪些计算被重复统计了？
▷🦆
题解提到了路径压缩，这个路径压缩的具体作用是什么？它如何影响并查集的效率？
▷