HackerRank 上的道路和图书馆 (DFS) 超时

Question

我知道已经有这样的问题了，但是答案并没有真正解决我的问题，因为我好像已经实现了，但是还是超时了。

HackerRank 上的任务是 here。

主要思想是在图中找到 "connected components"（即相互连接的节点组）。具体来说，统计有多少个，每个有多少个节点。我为此使用了一个简单的数组：connectedComponents[index] = numberOfNodesForAComponentAtIndex

问题是我的解决方案对大输入超时，但对较小的输入产生正确的结果。

我需要一些帮助来了解我的代码的哪一部分可以变得更快。

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

getNextCity 看起来可能很慢。

如果图中没有道路，那么调用getNextCity n次，每次都是O(n)次操作，所以整体复杂度为O(n^2)。

一种改进方法是只从最后找到的城市开始搜索，而不是每次都从 0 开始。这会将这部分的复杂度从 O(n^2) 降低到 O(n)，因为每个城市只会被测试一次。

HackerRank 上的道路和图书馆 (DFS) 超时

Roads And Libraries (DFS) on HackerRank times out

javascript

algorithm

depth-first-search