1319.Number of Operations to Make Network Connected === ###### tags: `Medium`,`DFS`,`BFS`,`Graph` [1319. Number of Operations to Make Network Connected](https://leetcode.com/problems/number-of-operations-to-make-network-connected/) ### 題目描述 There are `n` computers numbered from `0` to `n - 1` connected by ethernet cables `connections` forming a network where `connections[i]` = [$a_i$, $b_i$] represents a connection between computers $a_i$ and $b_i$. Any computer can reach any other computer directly or indirectly through the network. You are given an initial computer network `connections`. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return *the minimum number of times you need to do this in order to make all the computers connected*. If it is not possible, return `-1`. ### 範例 **Example 1:** ![](https://assets.leetcode.com/uploads/2020/01/02/sample_1_1677.png) ``` Input: n = 4, connections = [[0,1],[0,2],[1,2]] Output: 1 Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3. ``` **Example 2:** ![](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 ``` **Example 3:** ``` Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]] Output: -1 Explanation: There are not enough cables. ``` **Constraints**: * 1 <= `n` <= 10^5^ * 1 <= `connections.length` <= min(n * (n - 1) / 2, 10^5^) * `connections[i].length` == 2 * 0 <= $a_i$, $b_i$ < `n` * $a_i$ != $b_i$ * There are no repeated connections. * No two computers are connected by more than one cable. ### 解答 #### Python ```python= class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: if len(connections) < n - 1: return -1 graph = defaultdict(list) for u, v in connections: graph[u].append(v) graph[v].append(u) components = 0 visited = set() def dfs(node): visited.add(node) for nei in graph[node]: if nei not in visited: dfs(nei) for i in range(n): if i not in visited: dfs(i) components += 1 return components - 1 ``` > [name=Ron Chen][time=Thu, Mar 23, 2023] ```python= class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: if len(connections) < n - 1: return -1 sets_tag = [i for i in range(n)] sets = { i: {i} for i in range(n) } count = 0 for conn in connections: if sets_tag[conn[0]] == sets_tag[conn[1]]: continue sets[sets_tag[conn[0]]] |= sets[sets_tag[conn[1]]] replace_tag = sets_tag[conn[1]] for i in sets[sets_tag[conn[1]]]: sets_tag[i] = sets_tag[conn[0]] sets[replace_tag] = set() group_count = 0 for s in sets.values(): if len(s) > 0: group_count += 1 return group_count - 1 ``` >[name=gpwork4u][time=Fri, Mar 24, 2023] #### Javascript ```javascript= function makeConnected(n, connections) { if (connections.length < n - 1) return -1; const graph = new Array(n).fill(0).map(() => []); for (const [v1, v2] of connections) { graph[v1].push(v2); graph[v2].push(v1); } const visited = new Array(n).fill(false); let count = 0; // 從每台電腦出發開始找 for (let i = 0; i < n; i++) { if (visited[i]) continue; count++; const stack = [i]; // 標記相連的電腦 while (stack.length) { const node = stack.pop(); if (visited[node]) continue; visited[node] = true; for (const vertex of graph[node]) { stack.push(vertex); } } } return count - 1; } ``` > [name=Marsgoat][time=Thu, Mar 23, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)