[伯俊]1068ツリー-javascript

📌 質問する

https://www.acmicpc.net/problem/1068

📌 に答える

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

input.shift();
const parentInfo = input.shift().split(' ').map(Number);
const eraseNode = +input.shift();

let tree = [];
let cnt = 0;
let rootNode;

parentInfo.forEach((parentNode, idx) => {
  if (parentNode == -1) {
    rootNode = idx;
    return;
  }
  if (!tree[parentNode]) tree[parentNode] = [];
  tree[parentNode].push(idx);
});

const dfs = (node) => {
  if (rootNode == eraseNode) return 0;
  if (!tree[node]) {
    cnt++;
    return;
  }
  tree[node].forEach((nodeNum) => {
    if (nodeNum === eraseNode) {
      if (tree[node].length === 1) cnt++;
      return;
    }
    dfs(nodeNum);
  });
  return cnt;
};

console.log(dfs(rootNode));

✔アルゴリズム:DFS
✔tree[parentNode]の要素は、親ノード番号がparentNodeのノードです.
✔ルートノードからdfsの検索を開始し、リーフノードであればcntを追加します.現在のノードを親ノードとするノードがない場合は、リーフノードです.

if (!tree[node]) {
  cnt++;
  return;
}

✔子ノードが削除ノードの場合、親ノードに子ノードがない場合のみリーフノードになります.

if (tree[node].length === 1) cnt++;

✔難易度:標準プラチナ5