Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/03/23 16:33)推噓4(4推 0噓 0→)

留言4則, 4人參與, 2年前最新討論串270/719 (看更多)

1319. Number of Operations to Make Network Connected 有n台電腦，編號從0到n-1，透過網路線連接成一個網路。connections[i] = [ai, bi] 代表電腦ai和bi之間的連接，你可以切斷某些連接直接連接的兩台電腦之間的電纜，並將它們放置在任何一對未連接的電腦之間使它們連接。返回進行此操作的最小次數，可使所有電腦都連接。如果無法實現，則返回-1。 Example： https://assets.leetcode.com/uploads/2020/01/02/sample_2_1677.png

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]] Output: 2 思路： 1.要連結n個電腦最少需n-1條線所以可以先剪枝一次，如果n-1小於線的數量直接返回-1。 2.利用併查集把所有連結在一起的電腦合併成一個群組，獨立群組數量-1就是最少的操作次數。 Java Code： ----------------------------------------------- class Solution { public int makeConnected(int n, int[][] connections) { if (connections.length < n - 1) { return -1; } int[] root = new int[n]; for (int i = 0; i < n; i++) { root[i] = i; } for (int[] connection : connections) { int x = find(root, connection[0]); int y = find(root, connection[1]); if (x != y) { root[x] = y; } } Set<Integer> set = new HashSet<>(); for (int i = 0; i < n; i++) { set.add(find(root, root[i])); } return set.size() - 1; } private int find(int[] root, int x) { return root[x] == x ? x : (root[x] = find(root, root[x])); } } ----------------------------------------------- -- https://i.imgur.com/PIoxddO.jpg