# 1319. Number of Operations to Make Network Connected

• Time: $O(|V| + |E|)$, where $|E| = |\texttt{connections}|$
• Space: $O(|V| + |E|)$
  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 class Solution { public: int makeConnected(int n, vector>& connections) { // to connect n nodes, we need at least n - 1 edges if (connections.size() < n - 1) return -1; int numOfConnected = 0; vector> graph(n); unordered_set seen; for (const auto& conn : connections) { graph[conn[0]].push_back(conn[1]); graph[conn[1]].push_back(conn[0]); } for (int i = 0; i < n; ++i) if (seen.insert(i).second) { dfs(graph, i, seen); ++numOfConnected; } return numOfConnected - 1; } private: void dfs(const vector>& graph, int u, unordered_set& seen) { for (const int v : graph[u]) if (seen.insert(v).second) dfs(graph, v, seen); } }; 
  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 class Solution { public int makeConnected(int n, int[][] connections) { // to connect n nodes, we need at least n - 1 edges if (connections.length < n - 1) return -1; int numOfConnected = 0; List[] graph = new List[n]; Set seen = new HashSet<>(); for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int[] conn : connections) { graph[conn[0]].add(conn[1]); graph[conn[1]].add(conn[0]); } for (int i = 0; i < n; ++i) if (seen.add(i)) { dfs(graph, i, seen); ++numOfConnected; } return numOfConnected - 1; } private void dfs(List[] graph, int u, Set seen) { for (final int v : graph[u]) if (seen.add(v)) dfs(graph, v, seen); } }