题解：CF2284E My Mind Is Going

zhang_kevin · 2026-11-11 08:55:18 · 题解

对于原图 G 中的每个连通分量，如果 e_1 连接两个连通分量内的顶点，则由 G \cup \{e_1\} 是二分图这一性质可知 e_1 所在连通分量加入 e_1 后仍然是二分图，e_2 同理。那么如果 e_2 也是连接同一个连通分量中的两个顶点，则最终 G \cup \{e_1, e_2\} 是二分图，与题目条件矛盾；反之 e_2 一定连接两个不同的连通分量，但这两个连通分量在 e_1 加入后仍然是二分图，故把 e_2 的两个端点染为异色后一定存在合法的染色方案，此时新的图也是二分图与题目矛盾。因此我们最开始设「e_1 连接两个连通分量内的顶点」不成立，e_2 同理。故 e_1 和 e_2 必须连接两个不同的连通分量 A 和 B，且 e_1 = (a_1, b_1)、e_2 = (a_2, b_2)，其中小写字母顶点在对应大写字母的连通块内。

我们对原图的每个连通分量做 dfs，然后将每个连通分量内的节点按照 dfn 排序，再拼接成一个长为 n 的序列 p。由于这个序列是按照 dfn 排的，因此对于序列的任意前缀，满足这个前缀在原图连通。如果我们询问一段前缀 p_1 \sim p_i 的诱导子图是不是二分图，则回答“否”当且仅当这段前缀同时包含 a_1, a_2, b_1, b_2（否则一定存在合法染色方案）。故如果一段前缀对应的诱导子图是二分图，那么这段前缀之前的全部前缀对应的诱导子图都是二分图；反之，如果一段前缀对应的诱导子图不是二分图，则这段前缀之后的全部前缀对应的诱导子图都不是二分图。由此可见「一段前缀是不是二分图」满足单调性，可以二分找到第一个使得诱导子图不是二分图的前缀 [1, i]，这个 i 一定是 a_1, a_2, b_1, b_2 中 dfn 最大的那个点，不妨设为 b_2。

接下来，记 b_2 所在连通块为 B，其他全部连通块构成的子图为 C。此时我们以 b_2 为根，对连通块 B 再做一次 dfs，再按照 dfn 排序得到顶点序列 q，此时 q 依然满足任意一段前缀连通，且 q_1 = b_2。接下来我们进行类似上述过程的二分，但每次询问除了序列 q 的前缀之外要加上整个子图 C。这样我们询问的顶点集中一定包含 a_1, a_2, b_2（因为 b_2 是 q_1），找到第一个使得诱导子图不是二分图的位置即为 b_1。

然后类似上述二分，把整个连通块 B 固定为必选，然后在 C 上二分找到一个点 a，此时 a 一定是 a_1 或 a_2，但具体是谁不知道。那么我们再利用一次第二种询问，询问 a 和 b_1 是否有边。如果有边，则可以认为 e_1 = (a, b_1) 并输出；否则一定有 e_2 = (a, b_2)。

分析交互次数。第一次二分最多 \left\lceil \log_2 2000 \right\rceil = 11 次操作，第二次和第三次二分的范围大小分别是 |B| 和 |C|。由于 |B| + |C| = n \leq 2000，因此 |B| 和 |C| 一定有一个 \leq 1000。这样第二次和第三次的二分总询问次数不超过 \left\lceil \log_2 1000 \right\rceil + \left\lceil \log_2 2000 \right\rceil = 10 + 11 = 21 次。最后还需要一次第二种询问确定边，总询问次数最多 11 + 21 + 1 = 33 满足要求。

:::info[参考代码]{open}

提交记录：https://codeforces.com/contest/2284/submission/398086058。

#include<bits/stdc++.h>
#define fo(i, l, r) for(int i = (l); i <= (r); ++i)
using namespace std;
int T, n, m, dfn[2005], tot, p[2005], B[2005], dfnB[2005], totB, q[2005];
vector<int> e[2005];
inline void dfs(int u){
    dfn[u] = ++tot;
    for(auto v : e[u]){
        if(dfn[v]) continue;
        dfs(v);
    }
    return;
}
inline bool cmp(int x, int y){
    return dfn[x] < dfn[y];
}
inline void dfs2(int u){
    dfnB[u] = ++totB, B[u] = true;
    for(auto v : e[u]){
        if(dfnB[v]) continue;
        dfs2(v);
    }
    return;
}
inline bool cmp2(int x, int y){
    if(!dfnB[x]) return false;
    if(!dfnB[y]) return true;
    return dfnB[x] < dfnB[y];
}
inline bool cmp3(int x, int y){
    if(B[x]) return false;
    if(B[y]) return true;
    return dfn[x] < dfn[y];
}
signed main(){
    cin >> T; while(T--){
        cin >> n >> m;
        fo(i, 1, m){
            int u, v; cin >> u >> v;
            e[u].push_back(v), e[v].push_back(u);
        }
        fo(i, 1, n){
            if(!dfn[i]) dfs(i);
            p[i] = i;
        }
        sort(p + 1, p + 1 + n, cmp);
        int l = 1, r = n, b2 = p[n];
        while(l <= r){
            int mid = (l + r) >> 1;
            cout << "? 1 " << mid << ' ';
            fo(i, 1, mid) cout << p[i] << ' ';
            cout << endl;
            int res; cin >> res;
            if(res == 0){
                b2 = p[mid];
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        dfs2(b2); fo(i, 1, n) q[i] = i;
        sort(q + 1, q + 1 + n, cmp2);
        l = 1, r = totB; int b1 = q[totB];
        while(l <= r){
            int mid = (l + r) >> 1;
            cout << "? 1 " << mid + (n - totB) << ' ';
            fo(i, 1, mid) cout << q[i] << ' ';
            fo(i, 1, n) if(!B[i]) cout << i << ' ';
            cout << endl;
            int res; cin >> res;
            if(res == 0){
                b1 = q[mid];
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        sort(p + 1, p + 1 + n, cmp3);
        l = 1, r = n - totB; int a = p[n - totB];
        while(l <= r){
            int mid = (l + r) >> 1;
            cout << "? 1 " << mid + totB << ' ';
            fo(i, 1, mid) cout << p[i] << ' ';
            fo(i, 1, n) if(B[i]) cout << i << ' ';
            cout << endl;
            int res; cin >> res;
            if(res == 0){
                a = p[mid];
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        cout << "? 2 " << a << ' ' << b1 << endl;
        int res; cin >> res;
        cout << "! " << a << ' ' << (res ? b1 : b2) << '\n';
        tot = totB = 0; fo(i, 1, n) dfn[i] = B[i] = dfnB[i] = 0, e[i].clear();
    }
    return 0;
}

:::