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

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

解答例

隣接行列と隣接リストを作成して、それぞれ出力した。
隣接リストの重みの部分をi(m_ij) の形式で出力する必要があるが、可変長の二次元配列と"(" + k + ")"を用いて実装した。

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 と、その辺の重み k_i 
    const [a, b, k] = lines[i].split(" ").map(Number);
    //隣接配列
    g[a - 1][b - 1] = k;
    //隣接リスト
    h[a - 1].push([b - 1, "(" + k + ")"]);//指定された形式i(m_ij)
}

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

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

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

解答例(Python3の場合参考)

隣接行列を作成し、そこから隣接行列と隣接リストを出力した。
テンプレートリテラルを用いて指定された形式にした。

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);

//隣接行列
let g = Array(N).fill(0).map(v => v = Array(N).fill(0));

for (let i = 1; i <= M; i++) {
    //各辺の両端の頂点 a_i , b_i と、その辺の重み k_i 
    const [a, b, k] = lines[i].split(" ").map(Number);
    //隣接配列
    g[a - 1][b - 1] = k;
}

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

//隣接リストを出力
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (g[i][j] !== 0) {
      process.stdout.write(`${j}(${g[i][j]})`);//改行なし出力
    } 
  }
  console.log();//改行のみ
}