有向グラフの隣接行列と隣接リスト

今回は paiza の「有向グラフの隣接行列と隣接リスト」の問題に挑戦！

📘 問題概要

グラフの種類

• 有向グラフ
  • ノード（頂点）と向きのあるエッジ（辺）の集合
  • 辺には向きがある（a → b）
  • b → a とは別物

入力で与えられる情報

• N：頂点の数（1 ～ 100）
• M：辺の数
• 続く M 行：
  • a_i b_i
  • 頂点 a_i から b_i へ向かう辺を表す

作るもの（2種類）
① 隣接行列

• 大きさ：N × N
• 定義：
  • 頂点 i → j に辺がある → g[i-1][j-1] = 1
  • 辺がない → 0
• 0-indexed で管理
• 出力：
  • 各行を 0 と 1 を区切りなしで 出力
  • 合計 N 行

② 隣接リスト

• 大きさ：N 個の配列
• 定義：
  • 頂点 i → j に辺がある → g[i-1] に j-1 を追加
• 0-indexed で管理・出力
• 出力：
  • 各行は接続先の頂点番号を 昇順・区切りなし で出力
  • 接続先がない場合は 「空行」
  • 合計 N 行

出力全体の構成

• 合計 2 × N 行
  • 最初の N 行：隣接行列
  • 次の N 行：隣接リスト

入力例:

10 10
2 4
5 7
4 7
9 10
10 2
1 5
1 8
4 5
7 8
1 10

出力例:

0000100101
0001000000
0000000000
0000101000
0000001000
0000000000
0000000100
0000000000
0000000001
0100000000
479
3

46
6

7

9
1

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [N, M] = lines[0].split(' ').map(Number);
    const points = lines.slice(1).map(p => p.split(' ').map(Number));
    
    const gMatrix = Array.from({ length: N }, () => Array(N).fill(0)); // 隣接行列
    const gList = Array.from({ length: N }, () => []); // 隣接リスト
    
    for (let i = 0; i < M; i++) {
        const [a, b] = points[i];
        
        gMatrix[a-1][b-1] = 1;
        
        gList[a-1].push(b-1);
    }
    // 出力
    gMatrix.forEach(g => console.log(g.join('')));
    
    for (let i = 0; i < N; i++) {
        gList[i].sort((a, b) => a - b);
        for (const val of gList[i]) {
            process.stdout.write(String(val));
        }
        console.log();
    }
});

🔍 コードの流れ

1. 入力をすべて読み込む
   • readline を使って標準入力を1行ずつ lines 配列に保存する
   • 入力が終わったら close が呼ばれる
2. N（頂点数）と M（辺数）を取得
   • lines[0] から
   • N：頂点の数
   • M：辺の数
     を取り出す
3. 辺の情報を配列にまとめる
   • lines[1] 以降の M 行を
     • [始点, 終点] の配列として points に格納
4. 隣接行列と隣接リストを初期化
   • gMatrix
     • N × N の 0 で埋めた配列（隣接行列）
   • gList
     • 長さ N の空配列の配列（隣接リスト）
5. 辺情報を反映する
   • 各辺 (a → b) について
     • gMatrix[a-1][b-1] = 1
       → 隣接行列に辺を記録
     • gList[a-1].push(b-1)
       → 隣接リストに終点を追加
6. 隣接行列を出力
   • 各行を
     • 0 と 1 を 区切りなし で出力
7. 隣接リストを出力
   • 各頂点について
     • 接続先を昇順にソート
     • 値を 区切りなし で出力
     • 接続先がなければ空行を出力

📝まとめ

基本的にやることは、前回・前々回の隣接行列と隣接リストでやったことと同じだが、
違いは、前回は無向グラフで、今回は有向グラフであること。

よって、以下に注意して解く↓

• 1 つの辺につき、追加する情報が 1 つである
• 辺を受け取る際に向きを意識する必要がある