paizaラーニング レベルアップ問題集 Aランクレベルアップメニュー JavaScript 連結の判定

連結の判定 (paizaランク A 相当)

解答例(C++の場合参考)

幅優先探索をします。探索を終えて、全ての頂点に色が塗られていたら、連結しています。
色が塗られているかcolorで管理、隣接行列を使用、Qをキュー、nowを現在地とします。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [N, M] = lines[0].split(" ").map(Number);
let color = Array(N);//各頂点に色が塗れたか管理、0未、1済
for (let i = 0; i < N; i++) {
  color[i] = 0;//初期値は全て0未
}
//隣接行列
const graph = Array(N).fill(0).map(v => v = Array(N).fill(0));
for (let i = 1; i <= M; i++) {
    let [a, b] = lines[i].split(" ").map(Number);
    a--;
    b--;
    graph[a].push(b);
    graph[b].push(a);
}

//幅優先探索
let Q = [0]; //処理待ちの頂点を入れていくqueue、0スタート
color[0] = 1; //訪れた頂点を1済にしていく

while (Q.length > 0) {
    //処理待ちから取り出す
    let now = Q.shift();
    
    //行き先について
    for (let i = 0; i < graph[now].length; i++) {
        //訪れたことがないならば
        if (color[graph[now][i]] === 0) {
            color[graph[now][i]] = 1;//訪問済みに
            Q.push(graph[now][i]);//キューに入れる
        }
    }
}

let flag = true;//連結判定
//全て色塗られているかcolorを調べる。
for (let i = 0; i < N; i++) {
  if (color[i] === 0) {
    flag = false;
    break;
  }
}
 
//もし全ての頂点を訪れたならば連結している
console.log(flag ? "YES" : "NO");

解答例(Python3の場合参考)

深さ優先探索を適用しました。隣接リストを使用しました。pointをスタック、flagsを訪問管理とし、探索は頂点0からなのでpoints=[０]、flags[0]=1とします。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//頂点の数を表す整数 N , 辺の数を表す整数 M 
const [N, M] = lines[0].split(" ").map(Number);
//隣接リストg
const g = Array(N).fill(0).map(v => v = []);
//flags でその頂点を訪れたかを管理
let flags = Array(N).fill(0);

//通れる辺
for (let i = 1; i <= M; i++) {
    //各辺の両端の頂点 a_i , b_i 
    const [a, b] = lines[i].split(" ").map(Number);
    //配列
    g[a - 1].push(b - 1);
    g[b - 1].push(a - 1);
}

//points をスタックとして扱う
//探索を頂点 0 から始めるため points に 0 を入れ flags[0] を 1 に
points = [0];
flags[0] = 1;

//深さ優先探索
while (points.length > 0) {
    //stack の末尾を取り出す
    const point = points.pop();
    //隣接リストgについて行き先を調べる g[point][i]
    for (let i = 0; i < g[point].length; i++) {
        //まだ探索してなくて繋がっているなら points に追加します。
        if (flags[g[point][i]] === 0) {
            flags[g[point][i]] = 1;
            points.push(g[point][i]);
        }
    }
}//while

//未探索の頂点があれば NO と出力し、なければ YES と出力します。
if (flags.includes(0)) {
    console.log("NO");
} else {
    console.log("YES");
}

解答例(参考：Rubyの場合 解答例1 幅優先探索)

幅優先探索で、行き先探索にforEachを使用しました。
隣接行列を適用。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [N, M] = lines[0].split(" ").map(Number);

//隣接行列
const g = Array(n).fill(0).map(v => v = Array(n).fill(0));
for (let i = 1; i <= M; i++) {
    const [a, b] = lines[i].split(" ").map(Number);
    g[a - 1][b - 1] = 1;
    g[b - 1][a - 1] = 1;
}

let queue = [1]; //処理待ちの頂点を入れていく、0スタート
let visited = Array(N).fill(false); //訪れた頂点をtrueにしていく
//幅優先探索
while (queue.length > 0) {
    //処理待ちから取り出す
    let from = queue.shift();//探索元from
    //訪れた頂点をtrueに
    visited[from - 1] = true;
    
    //fromの行き先toについて
    g[from - 1].forEach((val, to) => { //valは隣接行列の0か１で、隣接しているかわかる
        //行き先が連結している　かつ　訪れたことがないならば
        if (val === 1 && visited[to] === false) {
            queue.push(to + 1);
        }
    });
}

//もし全ての頂点を訪れたならば連結している
console.log(visited.includes(false) ? "NO" : "YES");

forEachのところをforループでも大丈夫です。

//fromの行き先iについて、forを使用
    for (let i = 0; i < N; i++) {
        //行き先が連結している　かつ　訪れたことがないならば
        if (g[now - 1][i] === 1 && visited[i] === false) {
            queue.push(i + 1);
        }
    }

解答例(参考：Rubyの場合 解答例2 独立頂点と連結)

独立している頂点があったら連結でないという考え方で解きました。
こちらも隣接行列。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
const [N, M] = lines[0].split(" ").map(Number);
//隣接行列
const g = Array(n).fill(0).map(v => v = Array(n).fill(0));
for (let i = 1; i <= M; i++) {
    const [a, b] = lines[i].split(" ").map(Number);
    g[a - 1][b - 1] = 1;
    g[b - 1][a - 1] = 1;
}
//隣接ー独立ー連結の関係を調べる
let link = true; //連結しているか判定
//隣接行列において、独立している(隣接していない)点があるか調べる
g.forEach(row => {　//rowは調べる頂点を表す
   let isolation = true; //独立しているか判定
   row.forEach(val => { //valは頂点rowが隣接しているなら1してないなら0
      //もし隣接しているならば(valが0以外の1)、独立でない
      if (val !== 0) isolation = false;
   });
   //もし独立しているならば、連結していない
   if (isolation) link = false;
});
//連結しているか ？ YES NO
console.log(link ? "YES" : "NO");

forEachの二重ループはforの二重ループでもOKです。
breakが使えます。

for二重ループ

//隣接行列gの行＝各頂点について
for (let i = 0; i < N; i++) {
    let isolation = true; //独立しているか判定
    //各頂点の行き先について
    for (let j = 0; j < N; j++) {
        //もし隣接しているならば独立でない
        if (g[i][j] !== 0) isolation = false;
    }
    //もし独立した頂点があるならば、連結していない
    if (isolation) link = false;
    break;//forだとbreak使える。１つでも独立点が見つかったら、連結してない。
}