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.
- Roads and Libraries
- Discussions
Roads and Libraries
Roads and Libraries
Sort by
recency
|
14 Discussions
|
Please Login in order to post a comment
A very easy implementation using DFS and "Divide and Conquer Approach"
Java O(n+m)
JavaScript
The key is to recognize the following. If c_lib <= c_road, then we just build libraries at each city. Otherwise, you should always build a road if the road connects distinct components of the cities. Therefore, we should return c_lib*(the number of the components of the cities) + c_road*(n - the number of the components of the cities). Hence, the problem is a standard question to count the number of components of a given graph.