「ABC305F」 Dungeon Explore

题意

一张未知的 \(n\) 个点，\(m\) 条边的无向连通图。

从 \(1\) 号点开始，每次交互库给出与它相连的点编号，其中选出一个往下走。

在 \(2n\) 次交互内到达 \(n\) 号点。

分析

看到 \(2n\) 的次数，可以想到搜索。

遍历一遍的次数是 \(n\)，这一轮可以把图建出来。

正好剩下 \(n\) 次，可以直接再遍历一遍。

时间复杂度 \(O(n)\)。

这么简单的题怎么评绿的。

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define dbg(x) cout<<#x<<": "<<x<<"\n"
// static char buf[100],*p1=buf,*p2=buf,obuf[100],*p3=obuf;
// #define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,100,stdin),p1==p2)?EOF:*p1++
// #define putchar(x) (p3-obuf<100)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
const ll mod=1e9+7,maxn=1e5+5,maxt=505;
ll n,m,k,sta[maxn],top;
bool vis[maxn];
vector<ll>son[maxn];
inline void dfs(ll u){
    if(u==n)exit(0);
    vis[u]=1;k=read();
    for(ll i=1;i<=k;++i){
        ll v=read();
        son[u].push_back(v);
    }
    for(auto v:son[u]){
        if(!vis[v]){
            sta[++top]=u;cout<<v<<endl;
            dfs(v);--top;
        }
    }
    cout<<sta[top]<<endl;
    dfs(sta[top--]);
    return;
}
inline void solve(){
    n=read(),m=read();
    dfs(1);
}
signed main(){
    ll t=1;
    while(t--){
        solve();
    }
    // fwrite(obuf,p3-obuf,1,stdout);
    return 0;
}