問題概要

この問題はインタラクティブ問題である。

頂点数 $N$ 、辺数 $M$ の連結かつ単純な無向グラフがある。ただし最初の入力として与えられるのは $N, M$ の値のみである。

あなたは最初、頂点 1 にいる。頂点 $N$ へと移動したい。以下のやり取りを最大 $2N$ 回実行できる。

今いる頂点を $v$ として、 $v$ を出力する
頂点 $v$ に隣接する頂点のリストを入力として受け取る

制約

$2 \le N \le 100$
$N-1 \le M \le \frac{N(N-1)}{2}$

考えたこと

真っ先に、DFS の動きを再現すれば良いと考えた。

そして、そう思った瞬間に、以前にも似た問題を解いたことがあったのを思い出した。ABC 213 D だ。これも同じように DFS の動きをそのままシミュレートする問題だった。これとほとんど同じことができそうだ。

drken1215.hatenablog.com

基本的には、グラフを DFS しつつ、「今いる頂点に隣接する頂点がすべて探索済み」という状態になったら、前にいた頂点に戻る (= バックトラック) という部分を上手に実装すれば OK。

クエリ問い合わせ回数が $2N$ 以下になること

元のグラフが木でなかったとしても、DFS することで、DFS 木を構築できる。

今回の問題で訪れる頂点は、この DFS 木の Euler ツアーに他ならない。Euler ツアーにおいては、辺数が $N-1$ であるような各辺を 2 回ずつ辿ることになる。そのため、高々 $2(N-1)$ 回以内の移動で頂点 $N$ が見つけられると言える。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 最初の入力
    int N, M;
    cin >> N >> M;
    
    // 今いる頂点の隣接頂点を返す関数
    auto read = [&](int v) -> vector<int> {
        int num;
        cin >> num;
        vector<int> adj(num);
        for (int i = 0; i < num; ++i) cin >> adj[i];
        return adj;
    };
    
    // DFS
    vector<bool> seen(N+1, false);
    auto dfs = [&](auto self, int v) -> void {
        // 終了
        if (v == N) {
            string ok;
            cin >> ok;
            exit(0);
        }
        
        seen[v] = true;
        auto adj = read(v);
        for (auto v2 : adj) {
            if (seen[v2]) continue;
            cout << v2 << endl;
            self(self, v2);
            
            // back-tracking
            cout << v << endl;
            read(v);
        }
    };
    dfs(dfs, 1);
}