1. Build adjacency list (with bi-directional edges).
    2. For each city:
        if not visited city add 1 library and start a Breadth First Search starting from this city (new island).
    bfs:
        each city visited = 1 new road, skip cities already visited, add each city visited to list of visited cities.
    3. return min(num_cities * lib_cost, cities_and_roads_cost)

# BFS - O(V + E) - Time | O(2 * E) - Space
def get_roads_from_city(graph, city, visited):
    num_roads = 0
    neighbor_q = []
    visited.add(city)
    for neighbor in graph[city]:
        neighbor_q.append(neighbor)
    while len(neighbor_q) > 0:
        node = neighbor_q.pop(0)
        if node not in visited:
            num_roads += 1
            visited.add(node)
            if node in graph:
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        neighbor_q.append(neighbor)
    return num_roads, visited


def roadsAndLibraries(n, c_lib, c_road, cities):
    # Write your code here
    if n == 1:
        return c_lib
    
    graph = {}
    # Build Adjacency List
    for city in cities:
        neighbors = graph.get(city[0], [])
        neighbors.append(city[1])
        graph[city[0]] = neighbors
        
        neighbors = graph.get(city[1], [])
        neighbors.append(city[0])
        graph[city[1]] = neighbors
    
    for city in range(1, n + 1):
        if city not in graph:
            graph[city] = []
    
    # BFS
    def libraries_and_roads_cost(graph):
        num_roads = 0
        num_libraries = 0
        visited = set()
        for city in graph.keys():
            if city not in visited:
                roads, visited = get_roads_from_city(graph, city, visited)
                num_roads += roads
                num_libraries += 1
        return num_libraries * c_lib + num_roads * c_road
    
    libs_only = n * c_lib
    libs_roads = libraries_and_roads_cost(graph)
    return min(libs_only, libs_roads)

public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<Integer>> cities) {
        if(c_lib <= c_road || cities == null || cities.size() == 0)
            return c_lib * n;
        
        List<List<Integer>> adj = new ArrayList<>(n);
        for(int i = 0; i < n; i++){
            adj.add(new ArrayList<>());
        }
        for(int i = 0; i < cities.size(); i++){
            int u = cities.get(i).get(0) - 1;
            int v = cities.get(i).get(1) - 1;
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        boolean[] visited = new boolean[n];
        long clusters = 0;
        for(int i = 0; i < n; i++){
            if(visited[i]) continue;
            clusters++;
            Queue<Integer> subGraph = new LinkedList<>();
            subGraph.offer(i);
            while(!subGraph.isEmpty()){
                int curr = subGraph.poll();
                if(visited[curr]) continue;
                visited[curr] = true;
                //subGraph.addAll(adj.get(curr));
                for(Integer next : adj.get(curr)) {
                    if(!visited[next]) subGraph.add(next);
                }
            }
        }

        return (long)(clusters * c_lib) + (long)(n - clusters) * c_road;
    }