連結成分の大きさ《グラフ・DFS》

グラフ・DFSメニュー【連結の判定・グラフ全体の連結の判定・連結成分の数・連結成分の大きさ】

問題【STEP: 1】連結の判定
Task
無向グラフの頂点 s と頂点 t が連結しているならば Yes ・そうでなければ No と出力してね。

【連結の判定】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      if (now === t - 1) {
         connect = true;
         return;
      }
      const nexts = list[now];
      for (const next of nexts) {
         if (!seen.includes(next)) {
            dfs(next, [...seen, next]);
         }
      }
   };
   const [n, s, t] = lines.shift().split(' ').map(Number);
   const list = new Array(n).fill().map(e => []);
   for (let i = 0; i < n; i++) {
      const v = Number(lines.shift());
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   let connect = false;
// console.table(list);
   dfs(s - 1, [s - 1]);
   console.log(connect ? 'Yes' : 'No');
});
hogeちゃんの画像

うｐ。

top
問題【STEP: 2】グラフ全体の連結の判定
Task
無向グラフのグラフ全体が連結しているならば Yes 、そうでなければ No と出力してね。

【グラフ全体の連結の判定】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      seen[now] = true;
      if (!seen.includes(false)) {
         connect = true;
         return;
      }
      const nexts = list[now];
      for (const next of nexts) {
         if (!seen[next]) {
            dfs(next, seen);
         }
      }
   };
   const n = Number(lines.shift());
   const list = new Array(n).fill().map(e => []);
   for (let i = 0; i < n; i++) {
      const v = Number(lines.shift());
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   let connect = false;
   dfs(0, new Array(n).fill(false));
   console.log(connect ? 'Yes' : 'No');
});
hogeちゃんの画像

うｐ。

top
問題【STEP: 3】連結成分の数
Task
無向グラフの連結成分の数を出力してね。

【連結成分の数】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      seen[now] = true;
      const nexts = list[now];
      for (const next of nexts) {
         if (!seen[next]) {
            dfs(next, seen);
         }
      }
   };
   const n = Number(lines.shift());
   const list = new Array(n).fill().map(e => []);
   for (let i = 0; i < n; i++) {
      const v = Number(lines.shift());
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   let connect_num = 0;
   const seen = new Array(n).fill(false);
   for (let i = 0; i < n; i++) {
      if (!seen[i]) {
         connect_num++;
         dfs(i, seen);
      }
   }
   dfs(0, new Array(n).fill(false));
   console.log(connect_num);
});
hogeちゃんの画像

うｐ。

top
問題【FINAL】連結成分の大きさ
Task
無向グラフの各連結成分の頂点数が k 以下なら Yes ・そうでなければ No を出力してね。

【連結成分の大きさ】コード

reader.on('close', () => {
   const dfs = (now, seen) => {
      seen[now] = true;
      size++;
      // console.log(1, size);
      const nexts = list[now];
      for (const next of nexts) {
         if (!seen[next]) {
            dfs(next, seen);
         }
      }
   };
   const [n, k] = lines.shift().split(' ').map(Number);
   const list = new Array(n).fill().map(e => []);
   for (let i = 0; i < n; i++) {
      const v = Number(lines.shift());
      const a = lines.shift().split(' ').map(e => e - 1);
      list[i] = a;
   }
   // console.table(list);
   let under_k = true;
   const seen = new Array(n).fill(false);
   for (let i = 0; i < n; i++) {
      size = 0;
      if (!seen[i]) {
         dfs(i, seen);
         if (size > k) {
            under_k = false;
            break;
         }
      }
   }
   console.log(under_k ? 'Yes' : 'No');
});
hogeちゃんの画像

うｐ。

top

コメント