CF-1079-E2. Interactive Graph (Hard Version) · znzryb
## 题目大意
**题目名称**：E2. Interactive Graph (Hard Version)（交互式图困难版）
**题目描述**
这是一个交互题。
后台有一个包含 $n$ 个顶点和 $m$ 条边的**有向无环图（DAG）**，图中没有自环和重边。
你的任务是在最多进行 $n + m$ **次**询问的情况下，确定图中所有的边。
你可以进行如下格式的询问：
`? k`
系统会返回该图中按**字典序**排列的所有路径列表中的第 $k$ 条路径。
- **路径定义**：一个顶点序列 $u_1, u_2, \dots, u_l$，满足图中存在边 $(u_i, u_{i+1})$。
- **字典序定义**：序列 $a$ 小于序列 $b$ 当且仅当 $a$ 是 $b$ 的真前缀，或者在两者第一个不同的位置上，$a$ 的元素小于 $b$ 的元素。
- **返回格式**：系统首先返回路径长度 $q$。如果 $q=0$，表示不存在第 $k$ 条路径；否则，随后返回 $q$ 个整数表示该路径的顶点序列。
- **数据范围**：$1 \le n \le 30$，$1 \le k \le 2^{30}$。
**输出格式**
当你确定了所有边后，输出 `! m`，随后输出 $m$ 行，每行两个整数 $u, v$，代表存在一条从 $u$ 到 $v$ 的有向边。
**样例**
**Input**
```
3
5
1 1
2 1 2
3 1 2 4
3 1 2 5
2 1 3
3 1 3 4
3 1 3 5
1 2
1 3
1 4
1 5
1
0
2
1 1
1 2
2 2 1
```
**Output**
```
? 1
? 2
? 3
? 4
? 5
? 6
? 7
? 8
? 11
? 14
? 15
! 6
1 3
1 2
2 4
3 4
2 5
3 5
? 2
! 0
? 1
? 2
? 3
! 1
2 1
```
**样例解释**
以第一个测试用例为例：
- $n=5$。
- 程序依次询问了第 1, 2, ..., 15 条路径。
- 例如，`? 3` 返回了 `3 1 2 4`，表示字典序第 3 小的路径是 $1 \to 2 \to 4$。
- 通过这些路径信息，程序最终判断出图中有 6 条边，并输出了它们（如 $1 \to 3$, $1 \to 2$ 等）。
## 思路讲解
那么我们把我们可以记忆化的东西已经全部在图上标出来了。我们为什么要记忆化呢？其实我们的目标就在于，我们每次询问啊，我们都尽量想**比较好的去找到它的出边**，是吧？
如果有大量的这个路径，它实际上是没有什么信息的增量的。它大量的这个路径啊，就是它没有什么信息的增量。
比如说我们来看1~2这个路径，它就告诉了我们从1~2有一条出边。然后我们现在想要看1还有哪些出边，那么这个时候1~2~4、1~2~5实际上没有给我们带来信息的增量，但是1~3啊又给我们带来了信息的增量，但是1~3~4，1~3~5。但实际上又没有了信息的增量。所以我们就要想办法去跳过没有信息增量的东西。比如说1~2，它没有信息的增量。就是1~2以后，然后我们查找到 cnt 2实际上有3个，然后我们直接便利到1~2的时候，我们就直接跳到1~3，是不是就会好很多？
```cpp
auto solve=[&](auto && self,ll u,ll cur_k) -> void {
// 以前已经遍历到过了，这里就直接 return 就好了。
// 我们都是把返回值放在数组里面的，所以我们的返回类型是 void。
if (cnt_ls[u]) {
return;
}
vis[u]=1;
cnt_ls[u]=1;
while (true) {
vector<ll> res=query(cur_k+cnt_ls[u]);
auto it=find(all(res),u);
// 这个 it 不能够往后移的，这个迭代器不能够往后移的
// 那就说明没有 to 这个点了，我们就直接退出即可。
if (it==res.end() || it==prev(res.end())) {
return;
}
ll to=*next(it);
self(self,to,cur_k+cnt_ls[u]);
edges.push_back({u,to});
cnt_ls[u]+=cnt_ls[to];
}
};
ll cur_k=0;
for (ll u=1;u<=N;++u){
if (!vis[u]) {
solve(solve,u,cur_k+1);
}
// 注意，即便是已经被 vis 的点，就即便是已经遍历过的点，我们仍然需要去跳过这些点。
// 跳过的方式就是给目前的这个 K 加上这个 cnt_ls[u]。
cur_k+=cnt_ls[u];
}
```
## AC代码
AC
[https://codeforces.com/contest/2197/submission/362863587](https://codeforces.com/contest/2197/submission/362863587)
::: 源代码
```cpp
/**
* Problem: E2. Interactive Graph (Hard Version)
* Contest: Codeforces Round 1079 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2197/problem/E2
* Created: 2026-02-14 14:25:35
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct Edge {
ll u,v;
bool operator<(const Edge &o )const {
if (u!=o.u) return u<o.u;
return v<o.v;
}
bool operator==(const Edge & o) const {
return u==o.u && v==o.v;
}
};
void out_ans(const vector<Edge> &vec) {
cout<<"! "<<SZ(vec)<<endl;
for (auto &[u,v]:vec) {
cout<<u<<" "<<v<<endl;
}
}
void Solve() {
ll N;
cin >> N;
vector<ll> cnt_ls(N+2);
vector<char> vis(N+2);
vector<Edge> edges;
map<ll,vector<ll>> memo;
auto query=[&](ll k) -> vector<ll> {
auto it=memo.find(k);
if (it!=memo.end()) {
return it->second;
}
cout<<"? "<<k<<endl;
ll n;
cin>>n;
if (n==-1) {
exit(0);
}
vector<ll> res(n);
for (auto &v:res) {
cin>>v;
}
memo[k]=res;
return res;
};
auto solve=[&](auto && self,ll u,ll cur_k) -> void {
if (cnt_ls[u]) {
return;
}
vis[u]=1;
cnt_ls[u]=1;
while (true) {
vector<ll> res=query(cur_k+cnt_ls[u]);
auto it=find(all(res),u);
if (it==res.end() || it==prev(res.end())) {
return;
}
ll to=*next(it);
self(self,to,cur_k+cnt_ls[u]);
edges.push_back({u,to});
cnt_ls[u]+=cnt_ls[to];
}
};
ll cur_k=0;
for (ll u=1;u<=N;++u){
if (!vis[u]) {
solve(solve,u,cur_k+1);
}
// 注意，即便是已经被 vis 给，就即便是已经便利过的点，我们仍然需要去跳过这些点。
// 跳过的方式就是给目前的这个 K 加上这个 cnt_ls[u]。
cur_k+=cnt_ls[u];
}
sort(all(edges));
edges.resize(unique(all(edges))-edges.begin());
out_ans(edges);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2197/submission/362863587
1:
1 1
2:
2 1 2
3:
3 1 2 4
4:
3 1 2 5
5:
2 1 3
6:
3 1 3 4
7:
3 1 3 5
8:
1 2
9:
2 2 4
10:
2 2 5
11:
1 3
12:
2 3 4
13:
2 3 5
14:
1 4
15:
1 5
*/
```
:::
## 心路历程（WA，TLE，MLE……）
::: 错误的采用了比较复杂的编程方法。
采用了比较复杂的递归式的 sub 函数，这其实是会出问题的。就是我们以后写这个 solve 递归式 solve 函数，就是就是去找这个 q 点的这个逻辑，不应该放在子数当中，不应该放在子程序当中。那**你应该你自己去找这个东西**。
说白了就是**寻找停止点的逻辑**不应该放在**你的子函数当中**。
书写相关递归函数时，也可以尽量不要使用较为复杂的返回类型。可以直接就是**将返回值存在一数组**之中，我们整体的这个返回类型就是 void 就可以了。
```cpp
auto solve=[&](auto && self,ll u,ll cur_k) -> pair<ll,ll> {
vis.erase(u);
vector<ll> res=query(cur_k+1);
mx_cur_k=max(mx_cur_k,cur_k+1);
auto it=find(all(res),u);
// 异常情况处理
if (it==res.end() || it==prev(res.end())) {
if (res.empty()) {
return {0,0};
}else {
return {0,res.back()};
}
}
// 先不管异常情况，我们先想想正常情况怎么写
ll to=*next(it);
cnt_ls[u]=1;
edges.push_back({u,to});
while (true) {
ll cnt_to;
tie(cnt_to,to)=self(self,to,cur_k+cnt_ls[u]);
if (cnt_to==0) {
return {cnt_ls[u],to};
}
cnt_ls[u]+=cnt_to;
edges.push_back({u,to});
}
};
```
```cpp
/**
* Problem: E2. Interactive Graph (Hard Version)
* Contest: Codeforces Round 1079 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2197/problem/E2
* Created: 2026-02-14 11:04:59
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct Edge {
ll u,v;
bool operator<(const Edge &o )const {
if (u!=o.u) return u<o.u;
return v<o.v;
}
bool operator==(const Edge & o) const {
return u==o.u && v==o.v;
}
};
void out_ans(const vector<Edge> &vec) {
cout<<"! "<<SZ(vec)<<endl;
for (auto &[u,v]:vec) {
cout<<u<<" "<<v<<endl;
}
}
void Solve() {
ll N;
cin >> N;
vector<ll> cnt_ls(N+2);
set<ll> vis;
for (int i=1;i<=N;++i) {
vis.insert(i);
}
vector<Edge> edges;
map<ll,vector<ll>> memo;
auto query=[&](ll k) -> vector<ll> {
auto it=memo.find(k);
if (it!=memo.end()) {
return it->second;
}
cout<<"? "<<k<<endl;
ll n;
cin>>n;
if (n==-1) {
exit(0);
}
vector<ll> res(n);
for (auto &v:res) {
cin>>v;
}
memo[k]=res;
return res;
};
ll mx_cur_k=1;
auto solve=[&](auto && self,ll u,ll cur_k) -> pair<ll,ll> {
vis.erase(u);
vector<ll> res=query(cur_k+1);
mx_cur_k=max(mx_cur_k,cur_k+1);
auto it=find(all(res),u);
// 异常情况处理
if (it==res.end() || it==prev(res.end())) {
if (res.empty()) {
return {0,0};
}else {
return {0,res.back()};
}
}
// 先不管异常情况，我们先想想正常情况怎么写
ll to=*next(it);
cnt_ls[u]=1;
edges.push_back({u,to});
while (true) {
ll cnt_to;
tie(cnt_to,to)=self(self,to,cur_k+cnt_ls[u]);
if (cnt_to==0) {
return {cnt_ls[u],to};
}
cnt_ls[u]+=cnt_to;
edges.push_back({u,to});
}
};
while (!vis.empty()) {
solve(solve,*vis.begin(),mx_cur_k);
}
sort(all(edges));
edges.resize(unique(all(edges))-edges.begin());
out_ans(edges);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
1:
1 1
2:
2 1 2
3:
3 1 2 4
4:
3 1 2 5
5:
2 1 3
6:
3 1 3 4
7:
3 1 3 5
8:
1 2
9:
2 2 4
10:
2 2 5
11:
1 3
12:
2 3 4
13:
2 3 5
14:
1 4
15:
1 5
*/
```
:::