• + 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).