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. Practice
  2. Algorithms
  3. Graph Theory
  4. Roads and Libraries
  5. Discussions

Roads and Libraries

Sort 768 Discussions, By:

  • faqinghere
     + 50 comments

    It's easy to overthink this one.

    If the cost of a road is >= the cost of a library, just build a library at each node.

    Otherwise, use DFS to get the number of nodes (ct) in each connected component. Put 1 library in each component, and the total per component cost is simply ct-1 (a road to connect to each node in the compomnent) * cost of a road + cost of one library.

    You'll never put more than one library per component because once you're adding an additional node to a component, the cost of just building a road will always be cheaper than the cost of disconnecting the node (not building a road) and building a library instead.

  • cdmcgwire
     + 12 comments

    Spent 3 hours trying to figure out why mine failed half the tests.

    Bigger variables. Bigger variables all over.

  • mehmetmustafa
     + 5 comments

    Be careful about integer limitations! My java 8 solution:

    HashMap<Integer, ArrayList<Integer>> cityMap = new HashMap<>();
int n = scan.nextInt();
int m = scan.nextInt();
int libraryCost = scan.nextInt();
int roadCost = scan.nextInt();
for (int i = 1; i <= n; i++) {
	ArrayList<Integer> list = new ArrayList<Integer>();
	list.add(i);
	cityMap.put(i, list);
}

for (int a1 = 0; a1 < m; a1++) {
	int x = scan.nextInt();
	int y = scan.nextInt();
	ArrayList<Integer> list1 = cityMap.get(x);
	ArrayList<Integer> list2 = cityMap.get(y);
	if (list1 != list2) {
		list1.addAll(list2);
		list2.forEach(i -> cityMap.put(i, list1));
	}
}
if (libraryCost < roadCost)
	System.out.println((long) n * libraryCost);
else {
	long cost = 0;
	for (ArrayList<Integer> list : cityMap.values()) {
		int size = list.size();
		if (size > 0) {
			cost += libraryCost;
			cost += (size - 1) * roadCost;
			list.removeIf(i -> true);
		}
	}
	System.out.println(cost);
}

  • barretm99chaos
     + 6 comments

    my really short and concise solution :

    def roadsAndLibraries(n, c_lib, c_road, cities):
    if c_lib < c_road: return c_lib * n
    g, seen, ans = ddict(set), set(), 0
    for i,j in cities:
        g[i].add(j) 
        g[j].add(i)
    def dfs(i):
        seen.add(i) 
        return sum(dfs(j) for j in g[i] if j not in seen) + 1
    return sum((dfs(i) - 1) * c_road + c_lib for i in range(1, n + 1) if i not in seen)

  • eugalt
     + 2 comments

    If a road is not cheaper than a library you don't even need to build the graph and can just ignore the roads data. Otherwise, all you need to know is the number of connected components. And, btw, why do they use dollars in HackerLand? Don't they have their own currency?

Load more conversations