Minimum Operations to Connect Hospitals

JavaView on GFG

Intuition

Minimum edges to add to connect all hospital nodes in a graph. Count connected components, need components-1 edges.

Algorithm

1Build graph of hospitals. BFS/DFS or Union-Find to count connected components C. Answer = C - 1.

Common Pitfalls

•Standard connected components problem. MST adds exactly C-1 edges to connect C components.

Minimum Operations to Connect Hospitals.java

Java

// Approach: Minimum spanning tree (Kruskal or Prim) on the hospital graph.
// Time: O(E log E) Space: O(V)
import java.util.*;

class Solution {
    public int minConnect(int V, int[][] edges) {
        if (edges.length < V - 1)
            return -1;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());

        for (int edge[] : edges) {
            int u = edge[0];
            int v = edge[1];

            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        int count = -1;

        boolean vis[] = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (!vis[i]) {
                dfs(i, adj, vis);
                count++;
            }
        }

        return count;
    }

    public void dfs(int curr, ArrayList<ArrayList<Integer>> adj, boolean vis[]) {
        vis[curr] = true;

        for (int i = 0; i < adj.get(curr).size(); i++) {
            int neigh = adj.get(curr).get(i);
            if (!vis[neigh])
                dfs(neigh, adj, vis);
        }
    }
}

Was this solution helpful?