トレイルの通れない頂点

今回は paiza の「トレイルの通れない頂点」の問題に挑戦！

問題概要

・頂点 1 ～ n の番号がついた 無向グラフ が与えられる
・グラフは 隣接リスト形式 で入力される

・次の情報が与えられる
　・s：スタート頂点
　・t：ゴール頂点
　・S：通ってはいけない頂点の集合

・ここで トレイル を考える
　・同じ辺は2回使えない
　・頂点は何回通ってもよい

・ただし条件がある
　・S に含まれる頂点は通ってはいけない

・求めるもの
　・s から t までのトレイル
　・その中で 通る頂点数が最も多いもの

・複数ある場合
　・どれか1つを出力すればよい

・出力形式
　・通った頂点を 左から順にスペース区切りで出力
　・先頭は s、最後は t

・もし条件を満たすトレイルが存在しない場合
　・-1 を出力

入力例:

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

出力例:

1 2 5 4

✅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 k = Number(lines[1]);
    const S = lines[2].split(' ').map(Number);
    const forbidden = new Set(S);
    
    const graph = [];
    
    let idx = 3;
    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 - 1]) {
            if (forbidden.has(next)) continue;
            if (!edges[v][next]) {
                edges[v][next] = true;
                edges[next][v] = true;
                
                trail.push(next);
                
                if (next === t) {
                    trails.push([...trail]);
                    dfs(next, trail, edges); 
                } else {
                    dfs(next, trail, edges);
                }
                
                edges[v][next] = false;
                edges[next][v] = false;
                
                trail.pop();
            }
        }
    }
    
    dfs(s, [s], visit);
    
    let ans;
    let max = -Infinity;
    
    for (const a of trails) {
        if (a.length > max) {
            max = a.length;
            ans = a.join(' ');
        }
    }
    
    console.log(ans || '-1'); 
});

🔍コードの流れ

・入力を readline で受け取り、すべての行を lines 配列に保存する

・1行目から
　頂点数 n、開始頂点 s、終了頂点 t を取得する

・2行目から
　禁止頂点の数 k を取得する

・3行目から
　通ってはいけない頂点の集合 S を取得し、Set にして forbidden に保存する

・隣接リストを作る
　4行目以降の入力から、各頂点につながっている頂点を graph に保存する

・visit 配列を作る
　頂点同士の辺をすでに使ったかどうかを記録する

・条件を満たすトレイルを保存するための trails 配列を用意する

・dfs 関数を作る
　引数は
　現在の頂点 v
　これまで通った頂点の並び trail
　使用済みの辺 edges

・現在の頂点 v から行ける隣接頂点を順番に調べる

・もし次の頂点 next が禁止頂点集合 S に含まれていれば、その頂点には進まない

・その辺をまだ使っていなければ
　辺を使用済みにして
　trail に next を追加する

・もし next が終点 t なら
　そのトレイルを trails に保存する

・next を現在位置として、さらに探索を続ける

・探索から戻るとき
　使った辺を未使用に戻す
　trail の最後の頂点を削除する

・最初の探索として dfs(s, [s], visit) を実行する

・見つかったトレイルの中から
　頂点数が最大のものを探す

・最大のトレイルを出力する
　もし条件を満たすトレイルが存在しなければ -1 を出力する

📝まとめ

・トレイルの特徴
　・辺は再利用できない
　・頂点は再訪できる

・辺の使用管理
　・visit[a][b] の 2次元配列で管理

・DFSで全探索する

・探索中の経路を保存
　・trail 配列

・禁止頂点の処理
　・Set を使って
　・forbidden.has(next) で判定

・探索から戻るとき
　・辺を未使用に戻す
　・trail.pop() で経路を元に戻す

・t に到達したトレイルを保存する

・最後に
　・最も長いトレイルを選んで出力する