グラフの s,t トレイル

Posted at 2026-03-08

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

問題概要

🎯 やること

無向グラフが与えられる
始点 s
終点 t

👉 s から t までのトレイルの中で、最も頂点数が多いものを1つ出力する

🧩 トレイルとは？

❌ 同じ「辺」は使えない
⭕ 同じ「頂点」は何回通ってもよい

⚠️ 重要な追加条件

経路の最初は s
経路の最後は t
途中に s と t を含んではいけない

つまり：

s はスタートだけ
t はゴールだけ

📥 入力
1行目

n：頂点数
s：始点
t：終点

2行目以降（隣接リスト形式）

各頂点 i について：

隣接頂点の個数 v_i
隣接頂点の番号

📤 出力

s から t までのトレイル
頂点番号をスペース区切りで1行出力
最長のものを1つ
複数ある場合はどれでもよい

入力例：

出力例：

1 5 3 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 graph = [];
    
    // 隣接リスト作成
    for (let i = 2; i <= n * 2; i++) {
        if (i % 2 === 0) {
            graph.push(lines[i].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 (!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);
    
    let ans;
    let max = -Infinity;
    
    for (const a of trails) {
        if (a.length > max) {
            max = a.length;
            ans = a.join(' ');
        }
    }
    
    console.log(ans);
});

🔍 コードの流れ

① 入力を受け取る

n：頂点数
s：始点
t：終点

② 隣接リストを作る

各頂点の隣接頂点を読み込む
graph[i] に「頂点 i の隣接頂点一覧」を保存

③ 辺の使用状況を管理する配列を作る

visit[a][b] = true → 辺 (a,b) を使用済み
無向グラフなので両方向で管理

④ すべてのトレイルを保存する配列を用意

trails に s→t のトレイルを全部保存する

⑤ DFSで全探索

dfs(v, trail, edges) の流れ：

1️⃣ 現在の頂点 v の隣接頂点を順に見る

for (const next of graph[v - 1])

2️⃣ その辺をまだ使っていないか確認

if (!edges[v][next])

3️⃣ s を途中で通らないようにする

if (next === s) continue

👉 s は始点だけにする

4️⃣ 辺を使用済みにする

edges[v][next] = true
edges[next][v] = true

5️⃣ trail に追加

trail.push(next)

6️⃣ t に到達したか判定

もし next === t
- 今の trail を保存
それ以外なら
- 再帰でさらに探索

7️⃣ 元の状態に戻す処理

辺を未使用に戻す
trail.pop() で戻る

⑥ DFS開始

dfs(s, [s], visit)

⑦ 最長トレイルを選ぶ

trails の中から
長さが最大のものを探す

⑧ 出力

最長トレイルをスペース区切りで出力

📝まとめ

辺の再利用は禁止
頂点の再訪はOK
ただし s は始点だけ
t に着いたら終了
全探索して「最長」を選ぶ

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