Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/03/25 22:01)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串272/719 (看更多)

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