根付き木の根の変更《木・深さ優先探索》

木のメニュー 【距離が X の頂点・二頂点間の経路・木の同型判定・根付き木の根の変更】

問題【STEP: 1】距離が X の頂点
Task
木の情報と 頂点番号 A ・整数 X が与えられるので A から距離が X の頂点の番号を出力してね。

【距離が X の頂点】コード 1/2

reader.on('close', () => {
   const adjacency_List = (a, b) => {
      List[a].push(b);
      List[b].push(a);
   };
   const [N, A, X] = lines.shift().split(' ').map(Number);
   const range = new Array(N).fill(-1);  // 根 からの距離
   const Q = [A - 1];  // 幅優先探索のためのキュー Q (根から探索開始)
   range[A - 1] = 0;  // 根 は 距離 0
   const List = [];  // 隣接リスト
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 0; i < N - 1; i++) {
      const [A, B] = lines.shift().split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   while (Q.length) {  // Q が空になるまで繰り返し
      const now = Q.shift();  // Q の先頭の値を取り出して now とする
      const nexts = List[now];  // A に隣接した頂点
      nexts.forEach(next => {  // A に隣接した頂点のうち…
         if (range[next] === -1) {  // 未訪問（距離が確定していない）頂点の…
            range[next] = range[now] + 1;  // 距離を range[now] + 1 として…
            Q.push(next);  // その頂点を Q に追加
         }
      });
   }
   range.forEach((value, index) => {
      if (value === X) {  // value が X なら…
         console.log(index + 1);  // index + 1 を出力
      }
   });
});
hogeちゃんの画像

upしました。

top

【距離が X の頂点】コード 2/2

reader.on('close', () => {
   const adjacency_List = (a, b) => {
      List[a].push(b);
      List[b].push(a);
   };
   const bfs = (q, range) => {  // 幅優先探索
      if (!q.length) {  // q が空になれば…
         return range;  // 根からの距離を返す
      }
      const now = q.shift();  // q の先頭の値を取り出して now とする
      const next = List[now];
      for (const node of next) {  // now に隣接した頂点のうち…
         if (range[node] === -1) {  // 未訪問（距離が確定していない）頂点の…
            range[node] = range[now] + 1;  // 距離を range[now] + 1 として…
            q.push(node);  // その頂点を q に追加
         }　
      }
      return bfs(q, range);  // bfs(q, range) を呼び出す
   };
   const [N, A, X] = lines.shift().split(' ').map(Number);
   const Range = new Array(N).fill(-1);  // 根 からの距離
   const Q = [A - 1];  // 幅優先探索のためのキュー Q(根から探索開始)
   Range[A - 1] = 0;  // 根 は 距離 0
   const List = [];
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 0; i < N - 1; i++) {
      const [A, B] = lines.shift().split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   bfs(Q, Range);
   Range.forEach((value, index) => {
      if (value === X) {
         console.log(index + 1);
      }
   });
});
hogeちゃんの画像

upしました。

top
問題【STEP: 2】二頂点間の経路
Task
木の情報が与えられるので A から B までの経路上の頂点を通る順に出力して ね。

【二頂点間の経路】コード 1/2(幅優先順位探索)

reader.on('close', () => {
   const adjacency_List = (a, b) => {
      List[a].push(b);
      List[b].push(a);
   };
   const [N, A, B] = lines.shift().split(' ').map(Number);
   const List = [];
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 0; i < N - 1; i++) {
      const [A, B] = lines.shift().split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   const Q = [A - 1];  // 幅優先探索のためのキュー Q(根から探索開始)
   const stamp = new Array(N).fill(-1);
   stamp[A - 1] = 'start';
   while (Q.length) {  // Q が空になるまで繰り返し
      const now = Q.shift();  // Q の先頭の値を取り出して now とする
      const next = List[now];  // now に隣接した頂点
      for (const point of next) {  // now に隣接した頂点のうち…
         if (stamp[point] === -1) {  // 未訪問の頂点を…
            Q.push(point);  // Q に追加
            stamp[point] = now;  // point に隣接している根に近い頂点を記録
         }
      }
   }
   const route = [B - 1];  // 経路(遡る)
   let re_moved = B - 1;  // 経路を遡った地点
   while (stamp[re_moved] !== 'start') {  // スタートにたどり着くまで繰り返し
      re_moved = stamp[re_moved];  // 経路を遡った地点は re_moved に隣接している根に近い頂点
      route.unshift(re_moved);  // route の先頭に re_moved を追加
   }
   route.forEach(value => {
      console.log(value + 1);
   });
});
hogeちゃんの画像

upしました。

top

【二頂点間の経路】コード 2/2(深さ優先順位探索)

reader.on('close', () => {
   const dfs = (now, prev, route) => {
      visited[now] = true;  // now を訪問済みにする
      for (const next of List[now]) {  // 次の訪問先の候補が…
         if (next === prev || visited[next]) {  // 直前に訪問した頂点または訪問済みの頂点なら…
            continue;  // スキップ
         }
         visited[next] = true;  // next を訪問済みにする
         route.push(next + 1);  // route に next 保存
         if (next + 1 === B) {  // next が B (ゴール) なら…
            for (const i of route) {
               console.log(i);  // route の要素を出力
            }
            return;
         }
         dfs(next, now, route);
         route.pop();
         visited[next] = false;
      }
   };
   const [N, A, B] = lines.shift().split(' ').map(Number);
   const adjacency_List = (a, b) => {
      List[a].push(b);
      List[b].push(a);
   };
   const List = [];
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 0; i < N - 1; i++) {
      const [A, B] = lines.shift().split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   const visited = new Array(N).fill(false);
   dfs(A - 1, -1, [A]);
});
hogeちゃんの画像

upしました。

top
問題【STEP: 3】木の直径
Task
木についての情報が与えられるので 直径の値を求めてね。

【木の直径】コード

reader.on('close', () => {
   const bfs = (q, range) => {
      if (!q.length) {
         return range;
      }
      const now = q.shift();
      const next = List[now];
      for (const node of next) {  // A に隣接した頂点のうち…
         if (range[node] === -1) {
            range[node] = range[now] + 1;
            q.push(node);  // その頂点を Q に追加
         }　
      }
      return bfs(q, range);
   };
   const adjacency_List = (a, b) => {
      List[a].push(b);
      List[b].push(a);
   };
   const N = Number(lines.shift());
   const Range = new Array(N).fill(-1);  // 根 からの距離
   const Q = [N - 1];  // 幅優先探索のためのキュー Q(根から探索開始)
   Range[N - 1] = 0;  // 根 は 距離 0
   const List = [];
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 0; i < N - 1; i++) {
   const [A, B] = lines.shift().split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   bfs([N - 1], Range);
   const X = Range.indexOf(Math.max(...Range));
   const RangeX = new Array(N).fill(-1);  // 根 からの距離
   RangeX[X] = 0;  // 根 は 距離 0
   bfs([X], RangeX);
   console.log(Math.max(...RangeX));
});
hogeちゃんの画像

upしました。

top
問題【STEP: 4】木の同型判定
Task
2つの木の情報が与えられるので 双方が同型かどうかを判定してね。

【木の同型判定】コード

reader.on('close', () => {
   const N1 = Number(lines[0]);
   const N2 = Number(lines[N1]);
   let same = true;
   if (N1 !== N2) {
      same = false;
   } else {
      const N = N1;
      const List1 = [];
      const List2 = [];
      for (let i = 0; i < N; i++) {
         List1.push([]);
         List2.push([]);
      }
      for (let i = 1; i < N; i++) {
         const [A1, B1] = lines[i].split(' ').map(e => e - 1);
         const [A2, B2] = lines[i + N].split(' ').map(e => e - 1);
         List1[A1].push(B1);
         List1[B1].push(A1);
         List2[A2].push(B2);
         List2[B2].push(A2);
      }
      const L1 = [];
      const L2 = [];
      for (let i = 0; i < N; i++) {
         L1.push(List1[i].length);
         L2.push(List2[i].length);
      }
      const L1_sort = L1.sort((s, b) => s - b);
      const L2_sort = L2.sort((s, b) => s - b);
      for (let i = 0; i < N; i++) {
         if (L1_sort[i] !== L2_sort[i]) {
            same = false;
            break;
         }
      }
   }
   console.log(same ? 'YES' : 'NO');
});
hogeちゃんの画像
upしました。
top
問題【FINAL】根付き木の根の変更
Task
根付き木の情報と新たな根の頂点の番号・ K 個の頂点が与えられるので親の頂点を出力してね。

【根付き木の根の変更】コード

reader.on('close', () => {
   const adjacency_list = (start, end, list, a, b) => {
      for (let i = start; i <= end; i++) {
         list.push([]);
      }
      for (let i = start; i < end; i++) {
         [a, b] = lines.shift().split(' ').map(e => e - 1);
         list[a].push(b);
         list[b].push(a);
      }
      return list;
   };
   const bfs = (list, a, level, Q) => {
      level[a] = 0;
      while (Q.length) {  // Q が空になるまで繰り返し
         a = Q.shift();  // Q の先頭の値を取り出して a とする
         const nexts = list[a];  // a に隣接した頂点
         for (const next of nexts) {
            if (level[next] === -1) {
               level[next] = level[a] + 1;
               Q.push(next);
            }
         }
      }
      return level;
   };
   const [N, R] = lines.shift().split(' ').map(Number);
   const [K, r] = lines.splice(N-1,1)[0].split(' ').map(Number);
   const list = adjacency_list(1, N, [], 0, 0);
   const list_level_R = bfs(list, R - 1, new Array(N).fill(-1), [R - 1]);
   const list_level_r = bfs(list, r - 1, new Array(N).fill(-1), [r - 1]);
   list.forEach((value, index) => {
      for (let i = 0; i < value.length; i++) {
         const node = value[i];
         if (list_level_r[node] < list_level_r[index]) {
            value.splice(i, 1);
         }
      }
   });
   for (let i = N + 1; i <= N + K; i++) {
      const node = lines.shift() - 1;
      for (let i = 0; i < N; i++) {
         if (list[i].includes(node)) {
            console.log(i + 1);
            break;
         }
      }
   }
});
hogeちゃんの画像

upしました。

top

コメント