グラフの s,t トレイル 2

今回は paiza の「グラフの s,t トレイル 2」の問題に挑戦！

🧩 問題概要

🔽 与えられるもの
・頂点数 n の無向グラフ（1〜n）
・始点 s と終点 t（s ≠ t）
・各頂点の隣接リスト

🔽 グラフの特徴
・無向グラフ
・自己ループなし
・多重辺なし

🔽 やること
・頂点 s から頂点 t までのトレイルをすべて求める

🔽 トレイルの定義
・同じ辺は使えない
・頂点は何回通ってもOK

🔽 追加制約
・s と t は端点としてのみ使用
　→ s は最初だけ
　→ t は最後だけ
　→ 途中で出現したらNG

🔽 出力

・1行目：トレイルの総数
・2行目以降：各トレイル（頂点列）
　→ 必ず「s で始まり t で終わる」

入力例:

6 1 6
1
2
4
1 3 5 6
2
2 4
2
3 5
2
2 4
1
2

出力例:

3
1 2 3 4 5 2 6
1 2 5 4 3 2 6
1 2 6

✅OK例：

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

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

rl.on('close', () => {
    const [n, s, t] = lines[0].split(' ').map(Number);
    
    // 隣接リスト作成
    const graph = ['damy'];
    let idx = 1;
    for (let i = 0; i < n; i++) {
        const v = Number(lines[idx++])
        graph.push(lines[idx++].split(' ').map(Number));
    }
    
    const visit = Array.from({ length: n+1 }, () => Array(n+1).fill(false)); // 訪問済み（隣接行列）
    const trails = [];
    
    function dfs(v, trail, edges) {
        for (const next of graph[v]) {
            if (!edges[v][next]) {
                if (next === s) continue; // 条件：s, t を通過点として含まないトレイル
                
                edges[v][next] = true;
                edges[next][v] = true;
                
                trail.push(next);
                
                if (next === t) {
                    trails.push([...trail]); // ←コピー保存重要
                } else {
                    dfs(next, trail, edges);
                }
                
                edges[v][next] = false;
                edges[next][v] = false;
                
                trail.pop();
            }
        }
    }
    
    // スタートを含める
    dfs(s, [s], visit);
    console.log(trails.length);
    trails.forEach(t => console.log(t.join(' ')));
});

🔍コードの流れ

🔽 全体の流れ
・入力を読み取る（n, s, t とグラフ）
・隣接リスト graph を作る
・「使った辺」を管理する配列 visit を用意
・結果を入れる trails を用意
・DFSを開始（始点 s から）

🔽 DFSの流れ
・現在の頂点 v からスタート
・隣接する頂点 next を1つずつ見る

🔽 探索条件
・まだ使っていない辺（v → next）のみ進める
・next が s の場合はスキップ（通過点として含まない）]

🔽 次の頂点へ進むとき
・その辺を「使用済み」にする（両方向）
・trail に next を追加

🔽 分岐
・next が t の場合
　→ 経路完成 → trail をコピーして保存
・next が t でない場合
　→ さらにDFSで探索を続ける

🔽 戻るとき（バックトラッキング）
・使った辺を「未使用」に戻す
・trail の最後の頂点を削除

🔽 最後
・すべての探索が終わったら
・トレイルの数を出力
・各経路を1行ずつ出力

📝まとめ

前回との違いと注意点は、
・DFSの終了条件は t に到達したとき
・s, t を通過点として含まないトレイル