# Roads and libraries challenge

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 cities numbered from to . The cities are connected by 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 dollars, and the cost to build a library in any city is 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, , 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 (the number of cities), (the number of roads), (the cost to build a library), and (the cost to repair a road).

– Each line of the subsequent lines contains two space-separated integers, and , describing a bidirectional road connecting cities and .

**Constraints**

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 queries:

HackerLand contains cities connected by bidirectional roads. The price of building a library is and the price for repairing a road is .

The cheapest way to make libraries accessible to all is to:

– Build a library in city at a cost of .

– Repair the road between cities and at a cost of .

– Repair the road between cities and at a cost of .

This gives us a total cost of . Note that we don’t need to repair the road between cities and because we repaired the roads connecting them to city !

In this scenario it’s optimal to build a library in each city because the cost of building a library () is less than the cost of repairing a road ().

There are cities, so the total cost is .

**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 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 . Then if , we are better of with building additional libraries. If , we are better of with fixing 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)); } } }