Roads And Libraries (DFS) on HackerRank times out

Question

I know there is such a question already, but the answer doesn't really resolve my problem, as I seem to already have it implemented, yet it still times out.

The task on HackerRank is here.

The main idea is to find "connected components" in a graph (i.e. groups of mutually connected nodes). Specifically, count how many are there, and how many nodes is in each of them. I am using a simple array for this: connectedComponents[index] = numberOfNodesForAComponentAtIndex

The problem is that my solution times out for large input, yet yields correct results for smaller inputs.

I'd like some help understanding which part of my code could get faster.

function calculateCost(n, m, cLib, cRoad, roads) {
    // cost of road >= cost of library?
    if (cRoad >= cLib) {
        // build a library in each city
        return n * cLib;
    }

    // cost of road < cost of library?
    // find connected components: build a library in only 1, and connect all others with roads

    // infos needed:
    // 1) how many connected components
    // 2) how many cities in each connected component

    // array of numbers : each number represents the number of cities in connected component at index
    var connectedComponents = calculateConnectedComponents(n, m, roads);

    var cost = 0;   

    for (var i = 0; i < connectedComponents.length; i++) {
        var cc  = connectedComponents[i];
        cost += cLib + (cc - 1) * cRoad;
    }

    return cost;
}


function calculateConnectedComponents(n, m, roads) {
    // array of numbers : each number represents the number of cities in connected component at index
    var connectedComponents = [];

    // initialize all cities to not visited
    var notExpanded = new Set();
    var cities = [];

    for (var i = 1; i <= n; i++) {
        notExpanded.add(i);
        cities[i-1] = i;
    }

    var expansions = calculateExpansions(roads);

    while (notExpanded.size > 0) {
        // DFS
        var stack = [];

        // move on to the next city
        var start = getNextCity(cities);
        stack.push(start);


        // mark visited
        notExpanded.delete(start);
        cities[start-1] = -1;

        // calculate connected component
        var cc = 0;
        while (stack.length > 0) {
            process.stdout.write("STACK: " + stack.toString() + "\n");
            var city = stack.pop();   

            process.stdout.write("City: " + city.toString() + "\n");

            cc ++;

            // mark visited
            cities[city-1] = -1;

            var expanded = expand(city, expansions);
            process.stdout.write("EXP: " + expanded.toString() + "\n\n");

            for (var i = 0; i < expanded.length; i++) {
                if (notExpanded.has(expanded[i])) {
                    notExpanded.delete(expanded[i]);
                    stack.push(expanded[i]);
                }        
            }
        }

        connectedComponents.push(cc);
    }

    return connectedComponents;
}

function calculateExpansions(roads) {
    var expansions = {};

    for (var i = 0; i < roads.length; i++) {
        var road = roads[i];

        if (!(road.c1 in expansions)) {
            var exp = [];
            exp.push(road.c2);
            expansions[road.c1] = exp;
        } else {
            expansions[road.c1].push(road.c2);
        }

        if (!(road.c2 in expansions)) {
            var exp = [];
            exp.push(road.c1);
            expansions[road.c2] = exp;
        } else {
            expansions[road.c2].push(road.c1);
        }
    }

    return expansions;
}

function expand(city, expansions) {    
    if (expansions[city]) {
        return expansions[city];
    } else {
        return [];
    }
}


function getNextCity(cities) {
    for (var i = 0; i < cities.length; i ++) {
        if (cities[i] !== -1) {
            return cities[i];
        }
    }

    // error, should not happen
    return -1;
}

function main() {
    var q = parseInt(readLine());

    var costs = [];


    for(var a0 = 0; a0 < q; a0++){

        var n_temp = readLine().split(' ');
        var n = parseInt(n_temp[0]);
        var m = parseInt(n_temp[1]);
        var x = parseInt(n_temp[2]);
        var y = parseInt(n_temp[3]);

        var roads = [];

        for(var a1 = 0; a1 < m; a1++){
            var city_1_temp = readLine().split(' ');
            var city_1 = parseInt(city_1_temp[0]);
            var city_2 = parseInt(city_1_temp[1]);

            var road = {
                c1 : city_1,
                c2 : city_2
            };

            roads.push(road);
        }

        // n : number of cities
        // m : number of roads
        // x : cost of the library
        // y : cost of the road
        // roads: road connections
        costs.push(calculateCost(n, m, x, y, roads));   
    }

    process.stdout.write(costs.join("\n").toString());
}

Answer 1

One thing that looks potentially slow is getNextCity.

If there are no roads in the graph, then you will call getNextCity n times, and each time is O(n) operations, so overall the complexity will be O(n^2).

One way of improving this is to only search from the last city found, rather than starting from 0 each time. This would reduce the complexity of this part from O(n^2) to O(n) because each city would only be tested once.