We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Roads and Libraries
  2. Discussions

Roads and Libraries

Sort by

recency

|

33 Discussions

|

  • 1337er
     + 0 comments
    def roadsAndLibraries(n, c_lib, c_road, cities):
    # if libraries are cheaper we dont need to build roads
    if c_lib < c_road:
        return c_lib * n
    visited = [0] * n
    transport_stack = []
    cities_map = defaultdict(set)
    islands = 0
    # create a graph of road destinations
    # add both ways for bidirectional paths
    for i in cities:
        cities_map[i[0]-1].add(i[1]-1)
        cities_map[i[1]-1].add(i[0]-1)
    # iterate over the list of road edges
    for city in cities_map:
        if visited[city]:
            continue
        # if we have never been at this city before it is a new island
        islands += 1
        transport_stack.append(city)
        # travel the path of the road
        # if we find a new city add it to the stack
        while transport_stack:
            new_destination = transport_stack.pop(-1)
            if not visited[new_destination]:
                visited[new_destination] = 1
                if new_destination in cities_map:
                    for destination in cities_map[new_destination]:
                        if not visited[destination]:
                            transport_stack.append(destination)
		# if we nevered visited after looking at all the roads then it must be an island 
    islands += n - sum(visited)
    roads = n - islands
    # we need 1 road per city and 1 library per island
    result = (roads * c_road) + (c_lib * islands)
    return result

  • kasimovt
     + 0 comments

    python solution 

    # base case when building a lib is cheaper than a road
if c_lib <= c_road:
    return n*c_lib

# case when have to build roads

# initialize array to keep track of visited cities
    # 'w' not visited
    # 'g' being visited
    # 'b' finished visiting
visited = ['w'] * (n+1)

# initialize dictionary with all cities as keys
adj = {}
for city in range(1, n+1):
    adj[city] = []

# fill in the dictionary by recording adjacencies
for pair in cities:
    c1 = pair[0]
    c2 = pair[1]
    # record cities as adjacent
    adj[c1].append(c2)
    adj[c2].append(c1)


# integer list of components with ints representing their sizes
components = []

# depth first search
def dfs(city, count): 
    this_count = 1
    visited[city] = 'g'
    # go through all adjacent cities
    for adjacent in adj[city]:
        # if city has not been visited before 
        if visited[adjacent] == 'w':
            # run dfs on that city
            this_count += dfs(adjacent, count)
    # finished visiting this city
    visited[city] = 'b'
    return this_count


for city in range(1, n+1):
    if visited[city] == 'b':
        continue
    count = 0
    count = dfs(city, count)
    components.append(count)
print(components)

cost = c_lib * len(components)
for comp in components:
    cost += (comp-1)*c_road
return cost

    '''

  • goblin_dust
     + 0 comments

    C++ solution

    long roadsAndLibraries(int n, int c_lib, int c_road, vector> cities) {

    if (c_lib <= c_road) return (long) n*c_lib;

std::unordered_map<int, std::unordered_set<int>> adjacent;
std::vector<int> visited(n+1,false);

for (const auto & p : cities) {
    adjacent[p[0]].insert(p[1]);
    adjacent[p[1]].insert(p[0]);
}

std::function<void(int)> dfs;
dfs = [&](int i) {
    visited[i] = true;
    for (const auto & x : adjacent[i]) {
        if (!visited[x]) {
            dfs(x);
        }
    }
};

int citi_clusters = 0;
for (int i = 1; i <=n; ++i) {
    if (!visited[i]) {
        dfs(i);
        ++citi_clusters;
    }
}

long cost = (long)citi_clusters*c_lib + (long)(n-citi_clusters)*c_road;
return cost;

    }

  • gtai_quant
     + 0 comments
    def roadsAndLibraries2(n, c_lib, c_road, cities):
    # cost 1: c_lib * n
    if c_lib <= c_road:
        return c_lib * n
        
    # cost 2: c_lib * k + c_road * (n - k), where k is num of connected components
    # Initialize parent array for disjoint-set data structure
    parent = list(range(n+1))
    # Initialize rank array for union by rank optimization
    rank = [0] * (n + 1)
    
    # Find operation to recursively find the representative of a set
    def find_parent(city):
        if parent[city] == city:
            return city
        # Path compression: update parent pointers to point directly to the root
        parent[city] = find_parent(parent[city])
        return parent[city]
        
    # Union operation to merge two sets
    def union(city1, city2):
        a, b = find_parent(city1), find_parent(city2)
        if a == b:
            return
        # Union by rank: merge smaller tree into larger tree
        if rank[a] > rank[b]:
            parent[b] = a
        elif rank[a] < rank[b]:
            parent[a] = b
        else:
            parent[b] = a
            rank[a] += 1
    
    # Merge sets based on given roads
    for city1, city2 in cities:
        union(city1, city2)
        
    # Count the number of connected components (sets with representatives)
    k = sum(1 for city in range(1, n+1) if parent[city] == city)
    
    # Calculate cost based on the number of connected components
    return c_lib * k + c_road * (n - k)

  • gtai_quant
     + 0 comments
    from collections import defaultdict, deque

def roadsAndLibraries(n, c_lib, c_road, cities):
    """
    Cost 1 : one lib in each city
    Formula: c_lib * n
    
    Cost 2 : one lib per group of connected cities + connecting roads
    Formula: c_lib * k + c_road * (n - k), where k is number of groups
    
    If c_lib <= c_road, Cost 1 is lower; otherwise, Cost 2 is.
    """
    # Return Cost 1
    if c_lib <= c_road:
        return c_lib * n


    # Calculate Cost 2 below:
    
    # Initialize number of groups
    k = 0
    
    # Record direct connections for each city
    connections = defaultdict(set)
    for a, b in cities:
        connections[a].add(b)
        connections[b].add(a)
    
    # Track visited cities
    visited = [False] * (n + 1)
    
    # Identify connected components (groups of cities)
    for city in range(1, n + 1):
        if visited[city]:
            continue
        
        # Start a new group
        visited[city] = True
        k += 1
        
        # BFS to mark all cities in this group
        dq = deque([city])
        while dq:
            curr_city = dq.popleft()
            for linked_city in connections[curr_city]:
                if not visited[linked_city]:
                    visited[linked_city] = True
                    dq.append(linked_city)
                    
    # Return Cost 2
    return c_lib * k + c_road * (n - k)