paizaラーニング レベルアップ問題集 Aランクレベルアップメニュー JavaScript 有向グラフの隣接行列と隣接リスト

有向グラフの隣接行列と隣接リスト (paizaランク B 相当)

解答例

有向なので、1 つの辺につき、追加する情報が 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
let g = [];
for (let i = 1; i <= N; i++) {
    g.push(Array(N).fill(0));
}    
//隣接リストh
let h  = [];
for (let i = 1; i <= N; i++) {
    h.push([]);
}

for (let i = 1; i <= M; i++) {
    //各辺の始点 a_i と、終点 b_i 
    const [a, b] = lines[i].split(" ").map(Number);
    //配列
    g[a - 1][b - 1] = 1;//有向なので１つ
    //リスト
    h[a - 1].push(b - 1);//有向なので１つ
}

//隣接行列を出力
console.log(g.map(row => row.join("")).join("\n"));

//隣接リストの各行の頂点番号は昇順にソート
h.map(row => {
   row.sort((a,b) => {
       return a - b;
   });
});

//隣接リスト出力
console.log(h.map(row => row.join("")).join("\n"));