グラフのトレイル

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

問題概要

🎯 やること

• 完全無向グラフがある
• 始点 s
• 移動回数 k

👉 s からちょうど k 回移動するトレイルを 1つ出力する

🧩 トレイルとは？

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

👉 今までの「パス」と違う点が重要

📥 入力

• n：頂点数
• s：始点
• k：移動回数

📤 出力

• s から k 回移動した経路
• 頂点数は k+1 個
• 1つ見つかればOK（全列挙ではない）

入力例:

3 1 2

出力例:

1 2 3

✅OK例：

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

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

rl.on('close', () => {
    const [n, s, k] = lines[0].split(' ').map(Number);
    
    const graph = [];
    for (let i = 1; i <= n; i++) {
        const a = [];
        
        for (let j = 1; j <= n; j++) {
            if (i !== j) a.push(j);
        }
        
        graph[i] = a;
    }
    
    const visit = Array.from({ length: n+1 }, () => []); // 訪問済みリスト(隣接リスト)
    let cur = s;
    const trail = [s];
    
    for (let i = 0; i < k; i++) {
        const neighbors = graph[cur];
        while (true) {
            const next = neighbors[Math.floor(Math.random() * neighbors.length)];
            if (!visit[cur].includes(next)) {
                trail.push(next); 
                visit[cur].push(next);
                visit[next].push(cur);
                cur = next; 
                break;
            }
        }
    }
    
    console.log(trail.join(' '));
});

🔍 コードの流れ

① 入力を受け取る

• n（頂点数）
• s（始点）
• k（移動回数）

② 完全グラフを作る

• 各頂点 i について、自分以外の全頂点 j を隣接リストに追加
• これで「どの頂点からも他の全頂点へ行ける」状態になる

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

• visit[i] に「頂点 i からすでに使った辺の相手」を記録
• 無向グラフなので両方向で記録する

④ 初期設定

• 現在地 cur を s にする
• 経路 trail に s を入れる

⑤ k 回移動するループ

k 回繰り返す

1️⃣ 今いる頂点の隣接頂点を取得

• graph[cur] を取り出す

2️⃣ ランダムに次の頂点を選ぶ

• 隣接頂点の中からランダムに1つ選ぶ

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

• visit[cur] に含まれていないかチェック

4️⃣ 未使用なら

• trail に next を追加
• visit[cur] に next を記録
• visit[next] に cur を記録（無向なので両方向）
• 現在地 cur を next に更新
• ループを抜ける

⑥ 出力

• trail をスペース区切りで1行出力

📝まとめ

トレイルとは枝の反復を許さず頂点の反復を許す経路のこと