题干:
给定一张包含N个点、N-1条边的无向连通图,节点从1到N编号,每条边的长度均为1。假设你从1号节点出发并打算遍历所有节点,那么总路程至少是多少?
输入描述:
第一行包含一个整数N,1≤N≤10^5。
接下来N-1行,每行包含两个整数X和Y,表示X号节点和Y号节点之间有一条边,1≤X,Y≤N。
输出描述:
输出总路程的最小值。
输入例子:
4
1 2
1 3
3 4
输出例子:
4
解题思路:
这道题用数学的角度考虑,就是一共有N个点,N-1条路径,其实每一条路径都会被走两遍除了最长的那条路经,这样才能实现最短的路程遍历所有节点。也就是 2*(N-1)-最长路径长度
。
所以这道题的思路就变成了求最长路径的长度,用递归的方式,根据父节点找子节点,如果找得到子节点,长度加一,没找到就得到了该路径的最长距离,存入数组。最后在路径长度数组中找到最大值加入计算式输出即可。
JavaScript代码如下:
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let count = 0;
let N;
let paths = [];
let result = 0;
let results = [];
rl.on('line', (line) => {
if(count === 0) {
N = Number(line);
count ++;
} else if(count < N) {
paths.push(line.replace(/\s/g, ""));
// ['12', '13', '14'];
if(count === N-1) {
getChildNode('1');
console.log(2*(N-1) - Math.max.apply(this,results));
}
count ++;
} else {
rl.close();
}
})
function getChildNode(parentNode) {
const child = paths.filter(path => path.charAt(0) === parentNode);
if(child.length > 0) {
result ++;
for(i=0; i<child.length; i++) {
getChildNode(child[i].charAt(1));
}
} else {
results.push(result);
}
}
经测试,自测方案全部通过,但代码通过率仅为20%,代码逻辑以及迭代方法有待优化,如果有更好的方法可以留言告诉我谢谢!