Roads and Libraries

Sort by

recency

|

37 Discussions

|

  • + 0 comments
    long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) {
        if (cities.empty() || c_lib <= c_road) return (long)n * c_lib;
    
        map<int, stack<int>> cityMap;
        for (vector<int> road : cities) {
            int city1 = road[0], city2 = road[1];
            cityMap[city1].push(city2);
            cityMap[city2].push(city1);
        }
    
        vector<bool> visited(n + 1, false); 
        long libs = 0, rds = 0;
    
        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                libs++;
                stack<int> neighbors;
                neighbors.push(i);
                visited[i] = true;
    
                while (!neighbors.empty()) {
                    int curr = neighbors.top();
                    neighbors.pop();
    
                    while (!cityMap[curr].empty()) {
                        int neighbor = cityMap[curr].top();
                        cityMap[curr].pop();
    
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            neighbors.push(neighbor);
                            rds++;
                        }
                    }
                }
            }
        }
    
        return libs * c_lib + rds * c_road;
    }
    
  • + 0 comments

    C# solution using Union-Find Algorithm explained here: https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/

    class Result
    {
        // Uses the Union-Find algorithm to find the number of connected components.
        public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<int>> cities)
        {
            if (c_lib < c_road)
            {
                return (long)c_lib * n;
            }
            
            int[] parents = new int[n+1]; // n+1 because cities are 1-indexed.
            
            // Init with each node as its own parent.
            for (int i = 0; i <= n; i++)
            {
                parents[i] = i;
            }
            
            foreach (List<int> edge in cities)
            {
                Union(edge[0], edge[1], parents);
            }
            
            // Final round up. Now parents points to the root of each component.
            for (int i = 0; i <= n; i++)
            {
                parents[i] = Find(i, parents);
            }
            
            List<int> parentsList = parents.ToList();
            long components = parentsList.Distinct().LongCount() - 1; // -1 because parents[0] doesn't really exist.
            long edges = n - components;
            
            return (components * c_lib) + (edges * c_road);
        }
    
  • + 0 comments

    Solution in Java, quick and simple

    public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<Integer>> cities) {
            if(cities.isEmpty() || c_lib <= c_road) return 1L * n * c_lib;
            
            TreeMap<Integer, Stack<Integer>> cityMap = new TreeMap<>();
            for(List<Integer> connection: cities){
                int c1 = connection.get(0), c2 = connection.get(1);
                cityMap.computeIfAbsent(c1, k -> new Stack<>()).add(c2);
                cityMap.computeIfAbsent(c2, k -> new Stack<>()).add(c1);
            }
            
            long libs = n - cityMap.size(), roads = 0L;
            
            while(!cityMap.isEmpty()){
                // Start new cycle
                libs++;
                Stack<Integer> stack = cityMap.pollFirstEntry().getValue();
                while(!stack.isEmpty()) {
                    // DFS for connected cities
                    int c = stack.pop();
                    if(cityMap.containsKey(c)){
                        roads++;
                        stack.addAll(cityMap.remove(c));
                    }
                }
            }
            
            return libs * c_lib + roads * c_road;
        }
    
  • + 0 comments

    solution in C#:

        public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<int>> cities)
        {
            if(n == 0) return 0;
            if(c_lib <= c_road) return n * (long)c_lib;
            
            var connections = new Dictionary<int, List<int>>();
            for(int c = 1; c <= n; c++)
            {
                connections[c] = new List<int>();
            }
            foreach(var cityPair in cities)
            {
                connections[cityPair[0]].Add(cityPair[1]);
                connections[cityPair[1]].Add(cityPair[0]);
            }
            
            var queue = new Queue<int>();
            var visited = new HashSet<int>();
            var cost = 0L;
            
            for(int c = 1; c <= n; c++)
            {
                if(visited.Contains(c))
                {
                    continue;
                }
                
                cost += c_lib;
                queue.Enqueue(c);
                visited.Add(c);
                while(queue.Count > 0)
                {
                    var city = queue.Dequeue();
                    foreach(var neighbour in connections[city])
                    {
                        if(!visited.Contains(neighbour))
                        {
                            queue.Enqueue(neighbour);
                            visited.Add(neighbour);
                            cost += c_road;
                        }
                    }
                }
            }
            return cost;
        }
    
  • + 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