Solution: Python
from collections import defaultdict
def roadsAndLibraries(n, c_lib, c_road, cities):
if c_road > c_lib:
return n*c_lib
vset = set()
d = defaultdict(list)
group = []
def dfs(p):
vset.add(p)
numPoints = 1
if p in d:
for v in d[p]:
if not v in vset:
numPoints += dfs(v)
return numPoints
for u, v in cities:
d[u].append(v)
d[v].append(u)
for i in range(1, n+1):
if not i in vset:
group.append(dfs(i))
return c_lib * len(group) + c_road*(n-len(group))