0
我知道这个问题已经存在，但答案并不能真正解决我的问题，因为我似乎已经实施了它，但它仍然超时。HackerRank上的道路和图书馆（DFS）超时
HackerRank上的任务是here。
主要思想是在图表中找到“连通的组件”（即相互连接的节点组）。具体来说，统计有多少个节点，以及每个节点有多少个节点。我为此使用了一个简单的数组：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());
}