Sponsored
Sponsored
This approach uses the Union-Find (or Disjoint Set Union, DSU) data structure. It helps in efficiently finding the number of connected components in the network. Initially, every computer is its own component. We then iterate over each connection and unite the components of the two connected computers. Finally, we count how many separate components remain, since that will determine the number of cables needed to connect them.
Time Complexity: O(n + c), where n is the number of computers and c is the number of connections. Essentially, this is equivalent to O(c) given c > n. Space Complexity: O(n) for storing parent and rank arrays.
1class Solution:
2 def makeConnected(self, n: int, connections: List[List[int]]) -> int:
3 if len(
This Python solution focuses on employing the Union-Find with path compression and union by rank. We iteratively unite connected components and identify the number of disjoint sets remaining. The result is the count of operations needed, calculated by subtracting one from the number of components.
In this approach, we consider the computers and connections as a graph and use Depth-First Search (DFS) to determine the number of connected components. If there are at least n - 1 connections, it is possible to make the computers connected; otherwise, it isn't. Once the number of connected components is known, the number of operations required is the number of components minus one.
Time Complexity: O(n + c), where n is the number of computers and c is the connections. Space Complexity: O(n), managing the graph and visited structure.
using System.Collections.Generic;
public class Solution {
public int MakeConnected(int n, int[][] connections) {
if (connections.Length < n - 1) return -1;
List<List<int>> graph = new List<List<int>>();
for (int i = 0; i < n; i++) graph.Add(new List<int>());
foreach (var conn in connections) {
graph[conn[0]].Add(conn[1]);
graph[conn[1]].Add(conn[0]);
}
bool[] visited = new bool[n];
int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
components++;
DFS(i, visited, graph);
}
}
return components - 1;
}
private void DFS(int node, bool[] visited, List<List<int>> graph) {
visited[node] = true;
foreach (var neighbor in graph[node]) {
if (!visited[neighbor]) {
DFS(neighbor, visited, graph);
}
}
}
}The C# solution uses a DFS approach to traverse the graph formed by the computers and their connections. By continually traversing and marking visited nodes, we can count distinct components, allowing us to compute the necessary operations for connection.