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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int find(int* parent, int i) {
5 if (
This C code employs the Union-Find data structure. We first initialize every computer such that each is its own parent (leader of its own set). We process every connection to unite connected computers. Finally, we calculate the number of connected components by checking which computers are their own parents, and subtract one from this number to find the minimum number of required operations.
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 namespace std;
class Solution {
private:
void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor, visited, graph);
}
}
}
public:
int makeConnected(int n, vector<vector<int>>& connections) {
if (connections.size() < n - 1) return -1;
vector<vector<int>> graph(n);
for (auto& conn : connections) {
graph[conn[0]].push_back(conn[1]);
graph[conn[1]].push_back(conn[0]);
}
vector<bool> visited(n, false);
int components = 0;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs(i, visited, graph);
components++;
}
}
return components - 1;
}
};The C++ solution uses a DFS approach to determine the number of connected components. An adjacency list represents the graph, and DFS traverses each unvisited node to account for disconnected sections. The result is computed by the number of components minus one.