Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Roads and libraries challenge

Sharing is caring!

The Ruler of HackerLand believes that every citizen of the country should have access to a library. Ufortunately, HackerLand was hit by a tornado that destroyed all of its libraries and obstructed its roads! As you are the greatest programmer of HackerLand, the ruler wants your help to repair the roads and build some new libraries efficiently.

HackerLand has n cities numbered from 1 to n. The cities are connected by m bidirectional roads. A citizen has access to a library if:

  • Their city contains a library.
  • They can travel by road from their city to a city containing a library.

The following figure is a sample map of HackerLand where the dotted lines denote obstructed roads:

The cost of repairing any road is c_{road} dollars, and the cost to build a library in any city is c_{lib} dollars.

You are given queries, where each query consists of a map of HackerLand and value of and .

For each query, find the minimum cost of making libraries accessible to all the citizens and print it on a new line.

Input Format

The first line contains a single integer, q, denoting the number of queries. The subsequent lines describe each query in the following format:
– The first line contains four space-separated integers describing the respective values of n(the number of cities), m(the number of roads), c_{lib}(the cost to build a library), and c_{road}(the cost to repair a road).
– Each line i of the m subsequent lines contains two space-separated integers, u_i and v_i, describing a bidirectional road connecting cities u_i and v_i.

Constraints
1 \le q \le 10
1 \le n \le 10^5
0 \le m \le min(10^5, \frac{n(n-1)}{2})
1 \le c_{road}, c_{lib} \le 10^5
1 \le u_{i}, v_{i} \le 10^5
Each road connects two distinct cities.

Output Format
For each query, print an integer denoting the minimum cost of making libraries accessible to all the citizens on a new line.

Sample Input

2
3 3 2 1
1 2
3 1
2 3
6 6 2 5
1 3
3 4
2 4
1 2
2 3
5 6

Sample Output

4
12

Explanation
We perform the following q=2 queries:

HackerLand contains n = 3 cities connected by m = 3 bidirectional roads. The price of building a library is c_{lib} = 2 and the price for repairing a road is c_{road} = 1.

The cheapest way to make libraries accessible to all is to:
– Build a library in city 1 at a cost of x = 2.
– Repair the road between cities 1 and 2 at a cost of y = 1.
– Repair the road between cities 2 and 3 at a cost of y = 1.
This gives us a total cost of 2 + 1 + 1 = 4. Note that we don’t need to repair the road between cities 3 and 1 because we repaired the roads connecting them to city 2!

In this scenario it’s optimal to build a library in each city because the cost of building a library (c_{lib} = 2) is less than the cost of repairing a road (c_{road} = 5).

There are 6 cities, so the total cost is 6 \times 2 = 12.

Solution
We will regard the problem as a graph problem with the destroyed roads being the edges and the cities the vertices/nodes. As also illustrated in the sample graph above, a graph can consist of multiple clusters. We note a cluster as a set of nodes that are somehow connected to each other (directly or indirectly) but not to other nodes in different clusters.

Now that we know that we are looking at a graph problem and that a graph can consist of multiple clusters we will solve the problem for each cluster separately. We also know that for each cluster there must exist at least one library. So the cost will be at least c_{lib} multiplied by the number of clusters in the graph.

Once we have a library in each cluster we need to figure out whether we fix some of the roads in a cluster or just build a library in every city. Assume the number of cities in a cluster is k. Then if c_{lib} \textless c_{road}, we are better of with building k-1 additional libraries. If c_{lib} \textgreater c_{road}, we are better of with fixing k-1 roads.

So how do we figure out the clusters in the graph? We can either use Breadth-first search (BFS) or Depth-first search (DFS). We basically start a BFS or DFS from every non-visited node in the graph and annotate each visited node. When we start a new BFS/DFS from a non-visited node, we start a new cluster since we know that the current node wasn’t reachable from any node belonging to a previous cluster during a previous BFS/DFS. Each node reachable from the current node (directly or indirectly) gets added to the current cluster and marked as visited. Once we have visited all nodes, we are done.

Below is a an implementation of cluster separation using BFS. The function returns a list of clusters (each cluster is represented using a Set<Integer>). Although it is not necessary to actually collect the cluster nodes, the below function serves as an illustration on how to enumerate the clusters in a graph using BFS. For our problem purposes it suffices to just compute the size of every new cluster. A modification that only computes the sizes of the clusters can be easily made. The graph map links nodes (key) to a list of adjacent nodes (value).

private static List> cluster(int n, Map> graph) {
    boolean[] visited = new boolean[n + 1];
    List> clusters = new ArrayList<>();

    for (int node = 1; node <= n; node++) {
        if (!visited[node]) {
            // Start an new cluster
            Set cluster = new HashSet<>();

            // Do BFS
            Queue queue = new LinkedList();
            queue.add(node);

            while (!queue.isEmpty()) {
                Integer root = queue.poll();

                // Add node to cluster
                cluster.add(root);

                // Mark node as visited
                visited[root] = true;


                Set neighbors = graph.get(root);
                for (Integer adj : neighbors) {
                    if (!visited[adj]) {
                        queue.add(adj);
                    }
                }

            }

            if (!cluster.isEmpty()) {
                clusters.add(cluster);
            }
        }
    }

    return clusters;
}

For our final solution we are using DFS and also only compute the size of each cluster. The full and final code is listed below.

Full code

public class RoadsAndLibraries {
    private static long dfs(int root, Map> graph, boolean[] visited, long count) {
        visited[root] = true;

        Set neighbors = graph.get(root);
        for (Integer adj : neighbors) {
            if (!visited[adj]) {
                count = 1 + dfs(adj, graph, visited, count);
            }
        }

        return count;
    }

    private static long solve(int n, int m, long clib, long croad, Map> graph) {
        long ans = 0;

        boolean[] visited = new boolean[n + 1];
        for (int node = 1; node <= n; node++) {
            if (!visited[node]) {
                long clusterSize = dfs(node, graph, visited, 1);

                ans += clib;
                if (clib > croad) {
                    ans += ((clusterSize - 1) * croad);
                } else {
                    ans += ((clusterSize - 1) * clib);
                }
            }
        }

        return ans;
    }


    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);

        int tests = in.nextInt();
        for (int t = 0; t < tests; t++) {
            int n = in.nextInt(); // number of cities
            int m = in.nextInt(); // number of roads
            long clib = in.nextLong();
            long croad = in.nextLong();

            Map> graph = new HashMap<>();
            for (int node = 1; node <= n; node++) {
                graph.put(node, new HashSet<>());
            }

            for (int i = 0; i < m; i++) {
                int u = in.nextInt();
                int v = in.nextInt();
                graph.get(u).add(v);
                graph.get(v).add(u);
            }

            System.out.println(solve(n, m, clib, croad, graph));
        }
    }
}