This content originally appeared on DEV Community and was authored by Manasi Patil
Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀
100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney
Problem:
https://www.geeksforgeeks.org/problems/minimize-connections/1
Minimum Operations to Connect Hospitals
Difficulty: Medium Accuracy: 64.27%
You are given an undirected network of V hospitals numbered from 0 to V - 1, represented as a 2D array edges[][], where each element edges[i] = [u, v] denotes a direct connection between hospital u and hospital v.
In one operation, you are allowed to remove any existing link and reconnect it between two hospitals that are currently not directly or indirectly connected.
Your task is to determine the minimum number of operations required to make sure that all hospitals become connected, either directly or indirectly, using the given links.
Note: If it is impossible to connect all hospitals into a single network, return -1.
Examples:
Input: V = 4, E = 3, edges[][] = [[0, 1], [0, 2], [1, 2]]
Output: 1
Explanation: Remove the connection between hospitals 1 and 2 and connect the hospitals 1 and 3.
Input: V = 5, E = 4, edges[][] = [[0, 1], [0, 2], [2, 3], [3, 4]]
Output: 0
Explanation: All hospitals are already connected directly or indirectly. No rearrangement of connections is required.
Constraints:
1 ≤ V ≤ 103
0 ≤ E ≤ V*(V-1)/2
0 ≤ edges[i][0], edges[i][1] < V
Solution:
class Solution:
def minConnect(self, V, edges):
parent=list(range(V))
rank=[0]*V
def find(x):
if parent[x]!=x:
parent[x]=find(parent[x])
return parent[x]
def union(a,b):
pa,pb=find(a),find(b)
if pa==pb:
return False
if rank[pa]<rank[pb]:
parent[pa]=pb
elif rank[pb]<rank[pa]:
parent[pb]=pa
else:
parent[pb]=pa
rank[pa]+=1
return True
used=0
for u,v in edges:
if union(u,v):
used+=1
if len(edges)<V-1:
return -1
comp=set(find(i) for i in range(V))
need=len(comp)-1
extra=len(edges)-used
if extra>=need:
return need
return -1
This content originally appeared on DEV Community and was authored by Manasi Patil
Manasi Patil | Sciencx (2025-11-22T12:52:16+00:00) Day 50 of 100 days dsa coding challenge. Retrieved from https://www.scien.cx/2025/11/22/day-50-of-100-days-dsa-coding-challenge/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.