UOJ

分析

我们先假装原图是个二分图。

我们可以先想办法求出原图的一棵生成树，那么对其黑白染色即可求出答案。

一个暴力的做法是尝试删掉所有边，如果删掉某条边后连通性发生改变则这条边在生成树上，保留这条边，否则删掉这条边。这样子询问次数是 $\frac{n(n-1)}{2}$。

事实上我们可以每次二分下一条树边的位置：如果删掉 $[L,mid]$ 中的边后图仍连通则下一条树边在 $(mid,R]$ 中，否则在 $[L,mid]$ 中。这样子询问次数大概是 $2n\log n$。

我们稍微改变一下二分方式，对每个点二分出与哪些点的连边是树边。这样子询问次数就变成 $n\log n$ 了。

现在考虑如何判断原图是不是二分图。显然，如果原图不是二分图，则删去连接两个点集的非树边后一定存在一条树边使得删去这条树边后图仍连通。那么就很好判断了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include "graph.h"
#define re register
using namespace std;

const int N=200+10;

vector<int> E[N],ans;
vector<pair<int,int> > T,q;
int in[N][N],vis[N],col[N];

inline void dfs(int u) {
    vis[u]=1;
    for (re int v:E[u]) {
        if (vis[v]) continue;
        T.push_back(make_pair(u,v)),in[u][v]=in[v][u]=1;
        col[v]=col[u]^1,dfs(v);
    }
}

vector<int> check_bipartite(int n) {
    for (re int u=0;u<n;++u) {
        int v=u+1;
        while (v<n) {
            for (re int i=v;i<n;++i) q.push_back(make_pair(u,i));
            if (query(q)) break;
            for (re int i=v;i<n;++i) q.pop_back();
            int L=v,R=n-1;
            while (L<R) {
                int mid=(L+R)>>1;
                for (re int i=L;i<=mid;++i) q.push_back(make_pair(u,i));
                if (query(q)) L=mid+1;
                else R=mid;
                for (re int i=L;i<=mid;++i) q.pop_back();
            }
            E[u].push_back(L),E[L].push_back(u),v=L+1;
        }
    }
    dfs(0); q.clear();
    for (re int i=0;i<n;++i)
        for (re int j=i+1;j<n;++j)
            if (col[i]!=col[j]&&!in[i][j])
                q.push_back(make_pair(i,j));
    for (auto i:T) {
        q.push_back(i);
        if (query(q)) return {};
        q.pop_back();
    }
    ans.clear();
    for (re int i=0;i<n;++i) if (col[i]) ans.push_back(i);
    return ans;
}