Home > AI > Data Structure > Graph >

(HackerRank) Roads and Libraries

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))

Leave a Reply