Find connected components, then pick the cheaper option per component.
function roadsAndLibraries(n, c_lib, c_road, edges):
if c_road >= c_lib:
return n * c_lib
adj = [[] for _ in range(n + 1)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = [false] * (n + 1)
totalCost = 0
for city in range(1, n + 1):
if not visited[city]:
stack = [city]
visited[city] = true
size = 0
while stack is not empty:
node = stack.pop()
size += 1
for neighbor in adj[node]:
if not visited[neighbor]:
visited[neighbor] = true
stack.append(neighbor)
optionA = c_lib + (size - 1) * c_road
optionB = size * c_lib
totalCost += min(optionA, optionB)
return totalCost
time, space.