友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
2316. 统计无向图中无法互相到达点对数
给你一个整数 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 <= 105 -
0 <= edges.length <= 2 * 105 -
edges[i].length == 2 -
0 <= ai, bi < n -
ai != bi -
不会有重复边。
思路分析
利用 Map 构建整张图，然后在图中寻找每个块的大小 size，利用乘法原理，当前块的大小乘以寻找到的所有块的所有节点数量 total，就是遍历过的节点直接无法相互到达的数量，在遍历中，逐步求和，就是最终答案。
这道题还可以使用并查集来解决。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-21 17:39:01
*/
public long countPairs(int n, int[][] edges) {
List<Integer>[] graph = new List[n];
Arrays.setAll(graph, node -> new ArrayList<>());
for (int[] edge : edges) {
int a = edge[0];
int b = edge[1];
graph[a].add(b);
graph[b].add(a);
}
boolean[] visited = new boolean[n];
long result = 0;
for (int i = 0, total = 0; i < n; i++) {
if (!visited[i]) {
int size = dfs(i, graph, visited);
result += (long) size * total;
total += size;
}
}
return result;
}
private int dfs(int index, List<Integer>[] graph, boolean[] visited) {
visited[index] = true;
int result = 1;
for (Integer n : graph[index]) {
if (!visited[n]) {
result += dfs(n, graph, visited);
}
}
return result;
}