有向グラフの隣接行列と隣接リスト (paizaランク B 相当)
解答例
隣接行列と隣接リストをそれぞれ作成して、出力します。
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 = Array(N).fill(0).map(v => v = Array(N).fill(0));
//隣接リストh
let h = Array(N).fill(0).map(v => v = []);
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"));
//隣接リストの各行の頂点番号は昇順にソートして出力
console.log(h.map(row => row.sort((a, b) => a - b).join("")).join("\n"));
解答例2
隣接行列のみ作成し、隣接行列から隣接リストを出力します。
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 = Array(N).fill(0).map(v => v = 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][b - 1] = 1;
}
//隣接行列を出力
console.log(g.map(row => row.join("")).join("\n"));
//隣接行列から隣接リストを出力
console.log(g.map(row => row.map((val, i) => val === 1 ? i : "").join("")).join("\n"));