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

# Roads and Libraries

+ 0 comments Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Roads and Libraries Problem Solution

+ 0 comments C#

public static long RoadsAndLibraries(int n, int c_lib, int c_road, List<List<int>> cities) { long result = 0; foreach(ConnectedComponent connectedComponent in new Graph(n, cities).EnumerateConnectedComponents()) { result += Math.Min(connectedComponent.Size * c_lib, (connectedComponent.Size - 1) * c_road + c_lib); } return result; }

So, we just need to enumerate connected components of the graph here. It can be done with DFS or BFS. I personally prefer the second (mostly because BFS can be implemented easy without recursion).

+ 2 comments **C# is Power**

private static int Search(int node, bool[] visited, List<List<int>> nextNodes) { int citiesInGroup = 1; visited[node] = true; foreach (int item in nextNodes[node]) { if (!visited[item]) citiesInGroup += Search(item, visited, nextNodes); } return citiesInGroup; } public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<int>> cities) { if (c_lib <= c_road) return (long)c_lib * n; long cost = 0; bool[] visited = new bool[n + 1]; List<List<int>> nextNodes = new List<List<int>>(n + 1); for (int i = 0; i <= n; i++) { nextNodes.Add(new List<int>()); } foreach (var cityPair in cities) { int indexFor0 = cityPair[0]; int indexFor1 = cityPair[1]; nextNodes[indexFor0].Add(indexFor1); nextNodes[indexFor1].Add(indexFor0); } for (int i = 1; i <= n; i++) { if (!visited[i]) { int citiesInGroup = Search(i, visited, nextNodes); cost += c_lib + (long)(citiesInGroup - 1) * c_road; } } return cost; }

+ 0 comments Here is the solution of Roads and Libraries Click Here

+ 2 comments Hi everybody, can somebody explain why testcase q = 1, n = 5, m = 3, c_lib = 6, c_road = 1, [[1 2], [1 3], [1 4]] has answer 15. I thought should be 9 (because we have 3 road and 1 library). And also the question: why n = 5???? it should be 4 (cities = [1,2,3,4]).

Load more conversations

Sort 842 Discussions, By:

Please Login in order to post a comment