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.
I will share some intuition i used:
- We need to look at every sub graph of the cities such that each sub graph is a (potential) connected component.
- For each connected component, you can either buill one library per city and build no roads, or build one libaray and connect the rest of citis with mininum roads. There can be no in between that is optimum.
- For n citis, you alway only need n - 1 roads.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
An unexpected error occurred. Please try reloading the page. If problem persists, please contact support@hackerrank.com
Roads and Libraries
You are viewing a single comment's thread. Return to all comments →
I will share some intuition i used: - We need to look at every sub graph of the cities such that each sub graph is a (potential) connected component. - For each connected component, you can either buill one library per city and build no roads, or build one libaray and connect the rest of citis with mininum roads. There can be no in between that is optimum. - For n citis, you alway only need n - 1 roads.