隣接リスト

Posted at 2026-01-04

今回は paiza の「隣接リスト」の問題に挑戦！

🧩 問題概要

無向グラフが与えられる
（辺には向きがなく、自己ループ・多重辺はない）
頂点数 N、辺数 M、各辺 (a_i, b_i) が入力される
このグラフを隣接リストという形式で表現し、出力する

隣接リストとは

g は長さ N の 2 次元配列
g[i] には
👉 頂点 i+1 に隣接している頂点番号（0-indexed）を入れる
辺 (a, b) があるとき：
- g[a-1] に b-1 を追加
- g[b-1] に a-1 を追加
  （無向グラフなので両方向）

出力のルール

出力は必ず N 行
i 行目は g[i] の内容
各行の数字は昇順にソート
数字はスペースなしで連結
隣接頂点がない場合は改行のみ（空行）

入力例:

出力例:

✅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));
    
    // 隣接リスト（可変長2次元配列）
    const g = Array.from({ length: N }, () => []);

    for (const p of points) {
        const [a, b] = p;
        g[a-1].push(b-1);
        g[b-1].push(a-1);
    }

    for (let i = 0; i < N; i++) {
        g[i].sort((a, b) => a - b);
        for (const v of g[i]) {
            process.stdout.write(String(v));
        }
        console.log();
    }
});

🔍 コードの流れ

標準入力を 1 行ずつ lines 配列に格納する
入力が終わったら（close イベント）処理を開始する

入力の読み取り

1 行目から
- 頂点数 N
- 辺の数 M
  を取得する
2 行目以降を
- 辺の情報 [a, b] の配列として取得する

隣接リストの準備

長さ N の配列を作る
各要素は「隣接頂点を入れるための空配列」

g[0], g[1], …, g[N-1]

辺情報の登録（無向グラフ）

各辺 [a, b] について
- a-1 の配列に b-1 を追加
- b-1 の配列に a-1 を追加

これで双方向の隣接関係が記録される

隣接リストの出力

頂点 0 から N-1 まで順に処理する
各頂点について：
- 隣接頂点の番号を昇順にソート
- ソート済みの番号を改行せずに連結出力
- 最後に改行を 1 回出力する
  - 隣接がなければ空行になる

📝まとめ

グラフ構造について

無向グラフでは辺を両方向に登録する
隣接リストは、「つながっている頂点だけ」を持つ構造

配列・インデックスの考え方

入力は 1-indexed
内部処理・出力は 0-indexed
そのため常に、a-1, b-1 に変換して扱う

出力形式の重要ポイント

process.stdout.write
→ 改行しない（横に連結する）
console.log()
→ 改行だけを出力
この組み合わせで、
- 隣接あり → 数字 + 改行
- 隣接なし → 空行
  を自然に実現できる

※ 補足：役割分担をはっきりさせよう

① `process.stdout.write(String(v));`

改行しない
ただ文字をそのまま出力するだけ

例：

process.stdout.write("4");
process.stdout.write("7");
process.stdout.write("9");

出力：

（※ 改行なし）

② `console.log();`

必ず改行を1回出力
中身が空なら「改行のみ」

console.log();

出力：

\n

この2つを組み合わせた意味

for (const v of g[i]) {
  process.stdout.write(String(v));
}
console.log();

〇隣接ありの場合

write で数字を横につなげる
log で行を確定させる

479\n

〇隣接なしの場合

write は一度も呼ばれない
log だけ実行される

\n

👉 問題文どおり「改行のみ」

なぜ console.log(v) を使わないのか

もしこう書いたら：

for (const v of g[i]) {
  console.log(v);
}

出力は：

4
7
9

❌ 縦に並ぶ
❌ 行数が増える
❌ フォーマット崩壊

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up