→ v03516020: 大師 03/25 22:02
推 Che31128: 大師 03/25 22:03
推 uiojkl789: 找到新工作了嗎 03/25 22:04
2316. Count Unreachable Pairs of Nodes in an Undirected Graph
給定一個整數n和一個陣列edges，表示一個包含n個節點的無向圖，節點編號從0到n-1，
其中edges[i] = [ai，bi]表示節點ai和節點bi之間連通。
任意兩個節點稱為一個對(Pairs)，求出所有node彼此不連通的對共有幾個。
Example：
https://assets.leetcode.com/uploads/2022/05/05/tc-3.png
Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0
Explanation: 不存在彼此不連通的對
https://assets.leetcode.com/uploads/2022/05/05/tc-2.png
Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14
Explanation: 共有14個對node彼此不連通：
[[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]]
思路：
1.用併查集把所有連通的node合併成同個集。
2.把所有集的大小蒐集成一個列表。
3.每個集可以貢獻的不連通對數為 當前集所有點數量 * 沒連通的所有點數量
也就是 size * (n - size)，把每個集的貢獻相加除以二就是答案(去掉重複貢獻的)。
Java Code：
---------------------------------------------
class Solution {
public long countPairs(int n, int[][] edges) {
int[] root = new int[n];
for (int i = 0; i < n; i++) {
root[i] = i;
}
for (int[] edge : edges) {
int x = find(root, edge[0]);
int y = find(root, edge[1]);
if (x != y) {
root[x] = y;
}
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int x = find(root, i);
map.put(x, map.getOrDefault(x, 0) + 1);
}
List<Integer> list = new ArrayList<>();
for (int size : map.values()) {
list.add(size);
}
long ans = 0;
for (int size : list) {
ans += (long)size * (n - size);
}
return ans / 2;
}
private int find (int[] root, int x) {
return (root[x] == x) ? x : (root[x] = find(root, root[x]));
}
}
---------------------------------------------
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1679752899.A.CA7.html