题解：CF1033E Hidden Bipartite Graph

· · 题解

先考虑找一个生成树。维护两个集合 S=\{1\},T=\{2,3,4,\cdots,n\}，然后考虑每次找一条 S 里的点向 T 里点的连边。对于这个可以先二分出 T 里哪个点（设为 x）与 S 里有连边，然后再二分是 S 里的哪个点 y 与 x 有连边。这样可以用 2\log |S|+2\log |T| 的次数得到一条 S 向 T 连的边。之后我们把 x 加到 S 里，从 T 里删掉，然后连一条边 (x,y)。

得到生成树之后直接黑白染色就可以得到这个图的两部分，然后判断原图是不是二分图可以直接询问两个部分自己里面有没有连边。如果两部分都没连边说明确实是二分图。

如果有连边，不妨设有连边的是左部点 L，那我们可以通过类似 APIO 2025 T1 的手段在 O(\log |L|) 的时间里找到这条边。具体的，把 L 平均分成两部分，然后询问两部分里面有没有边，如果其中一部分有边就直接递归，否则一定是两部分点之间的连边，直接套用上面的方法就行了。

找到这条边之后，相当于是往生成树上加了一条边，这一定会形成一个奇环，于是只需要找树上这两个点之间的路径输出即可。

总的询问次数是 4n\log n，比较极限。注意写代码的时候如果你只询问一个点的话可以直接跳过，可以省下不少询问次数。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define fi first
#define se second

int n, cc, col[605], vis[605], nxt[605];
vector<int> g[605], S, T, lc, rc;

int qry(vector<int> vec) {
    int sz = (int)vec.size();
    if (sz <= 1) return 0; 
    cout << "? " << sz << endl;
    for (int i = 0; i < sz; i++) cout << vec[i] << " ";
    cout << endl;
    int x; cin >> x; return x;
}

pii link(vector<int> l, vector<int> r) {
    int L = 0, R = (int)l.size() - 1, cr = qry(r);
    vector<int> res = r, tmp;
    while (L != R) {
        int mid = (L + R) >> 1;
        for (int i = L; i <= mid; i++) res.push_back(l[i]), tmp.push_back(l[i]);
        int tot = qry(res), cl = qry(tmp);
        for (int i = L; i <= mid; i++) res.pop_back(), tmp.pop_back();
        if (tot == cl + cr) L = mid + 1;
        else R = mid;
    }
    cr = l[L], L = 0, R = (int)r.size() - 1, res = {cr};
    while (L != R) {
        int mid = (L + R) >> 1;
        for (int i = L; i <= mid; i++) res.push_back(r[i]), tmp.push_back(r[i]);
        int tot = qry(res), cl = qry(tmp);
        for (int i = L; i <= mid; i++) res.pop_back(), tmp.pop_back();
        if (tot == cl) L = mid + 1;
        else R = mid;
    }
    return {cr, r[L]};
}

pii find(vector<int> vc) {
    if (vc.size() == 2) return {vc[0], vc[1]};
    int mid = ((int)vc.size() - 1) >> 1;
    vector<int> vl, vr;
    for (int i = 0; i <= mid; i++) vl.push_back(vc[i]);
    if (qry(vl)) return find(vl);
    for (int i = mid + 1; i < (int)vc.size(); i++) vr.push_back(vc[i]);
    if (qry(vr)) return find(vr);
    return link(vl, vr);
}

bool dfs(int u, int f, int rt) {
    if (u == rt) return true;
    bool flg = false;
    for (int v : g[u]) if (v != f) {
        if (dfs(v, u, rt)) flg = true, nxt[u] = v;
    }
    cc += flg;
    return flg;
}

int main() {
    cin >> n;
    S.push_back(1), lc.push_back(1); for (int i = 2; i <= n; i++) T.push_back(i);
    while ((int)S.size() != n) {
        pii p = link(S, T);
        T.erase(find(T.begin(), T.end(), p.se)), S.push_back(p.se);
        g[p.fi].push_back(p.se), g[p.se].push_back(p.fi);
        col[p.se] = col[p.fi] ^ 1;
        if (col[p.se]) rc.push_back(p.se);
        else lc.push_back(p.se);
    }
    int cl = qry(lc), cr = qry(rc);
    if (!cl && !cr) {
        cout << "Y " << lc.size() << endl;
        for (int i : lc) cout << i << " ";
        return cout << endl, 0;
    }
    if (!cl) swap(lc, rc);
    pii p = find(lc); dfs(p.fi, 0, p.se);
    cout << "N " << cc + 1 << endl;
    for (int i = p.fi; i != p.se; i = nxt[i]) cout << i << " ";
    return cout << p.se << endl, 0;
}