UOJ461 新年的Dog划分

首先考虑搞出来原图的一棵生成树，直接把这棵生成树二分图染色即可。

一个比较显然的方法是在边集中二分，把所有的边依次排开，假设当前位于边x，在保留已经确定了的生成树上的边的情况下，删掉x之前的所有边，然后看原图是否联通。

使得x尽可能靠右即可。

这样一定可以搞出来n-1条边。

如何判断奇环?

把树二分图染色后，枚举一条树边，然后删掉这条树边和所有二分图中连接两个点集的边，如果此时图仍然联通说明存在奇环。

这样的询问次数大概是$(n-1)log(n^2)=O(2nlogn)$的，过不去。

然后我们尝试考虑对于点进行二分。

从1号点开始BFS。

假设当前点为vtx，没访问过的并且和vtx不在一条树边上的点v纳入二分范围。

设这个点集为S。

如果所有的边$(vtx,v)(v\in S)$全部删除后原图仍然联通，那么就直接把这些边纳入删除集合，然后队列弹出点vtx。

否则二分一个位置x，使得位置在x之前的所有边删掉后都不会使得图不连通，但是删掉x后图就不连通。

此时把x之前的所有边纳入删除集合，$(vtx,x)$纳入树边。

然后接着二分x后面的点即可（实际实现就是队列不弹出点vtx）。

询问次数在$O(nlogn)$级别的。

#include <assert.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include "graph.h"
using int_t = int;
using pair_t = std::pair<int_t, int_t>;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 200;

std::vector<pair_t> result;
std::vector<pair_t> removes;
bool onTree[LARGE + 1][LARGE + 1];
bool removed[LARGE + 1][LARGE + 1];
int_t n;
//删除已知的待删除边和vtx编号在id之前的所有边是否联通
bool myCheck(int_t vtx, const std::vector<int_t>& to, int_t id) {
    std::vector<std::pair<int, int>> next = removes;
    for (int_t i = 0; i <= id; i++) {
        if (onTree[vtx][to[i]] == false) next.push_back(pair_t(vtx, to[i]));
    }
    for (auto& p : next) {
        p.first -= 1;
        p.second -= 1;
        assert(p.first != p.second);
    }
    bool result = query(next);
    return result;
}
void BFS() {
    static bool inq[LARGE + 1];
    std::queue<int_t> queue;
    queue.push(1);
    inq[1] = true;
    while (queue.empty() == false) {
        int_t front = queue.front();

        std::vector<int_t> to;
        for (int_t i = 1; i <= n; i++) {
            if (i != front && inq[i] == false && removed[front][i] == false)
                to.push_back(i);
        }
        int_t left = 0, right = to.size() - 1;
        int_t result = to.size();
        //所有边保留仍然联通,直接标记成废边
        if (myCheck(front, to, right)) {
            for (int_t x : to) {
                removed[x][front] = removed[front][x] = true;
                removes.push_back(pair_t(x, front));
            }
        } else {
            while (left <= right) {
                int_t mid = (left + right) / 2;
                if (!myCheck(front, to, mid)) {
                    right = mid - 1;
                    result = std::min(result, mid);
                } else {
                    left = mid + 1;
                }
            }
            for (int_t i = 0; i < result; i++) {
                removed[to[i]][front] = removed[front][to[i]] = true;
                removes.push_back(pair_t(to[i], front));
            }
        }
        if (result != to.size()) {
            onTree[front][to[result]] = onTree[to[result]][front] = true;
            queue.push(to[result]);
            inq[to[result]] = true;
        } else {
            queue.pop();
        }
    }
}
std::vector<int_t> graph[LARGE + 1];
int_t color[LARGE + 1];
void DFS(int_t vtx, int_t from = -1) {
    for (int_t to : graph[vtx]) {
        if (to != from) {
            color[to] = color[vtx] ^ 1;
            DFS(to, vtx);
        }
    }
}
bool removeCheck(pair_t edge) {
    std::vector<pair_t> next;
    for (int_t i = 1; i <= n; i++) {
        if (color[i] == 0) {
            for (int_t j = 1; j <= n; j++) {
                if (color[j] == 1 && onTree[i][j] == false) {
                    next.push_back(pair_t(i, j));
                }
            }
        }
    }
    next.push_back(edge);
    for (auto& p : next) {
        p.first -= 1;
        p.second -= 1;

        assert(p.first != p.second);
    }
    bool result = query(next);
    return result;
}
std::vector<int> check_bipartite(int vsize) {
    ::n = vsize;
    BFS();
    std::vector<pair_t> treeEdges;
    for (int_t i = 1; i <= n; i++) {
        for (int_t j = i + 1; j <= n; j++) {
            if (onTree[i][j]) {
                graph[i].push_back(j);
                graph[j].push_back(i);
                treeEdges.push_back(pair_t(i, j));
            }
        }
    }
    DFS(1);
    for (const auto& edge : treeEdges) {
        if (removeCheck(edge)) {
            return std::vector<int_t>();
        }
    }
    std::vector<int_t> result;
    for (int_t i = 1; i <= n; i++)
        if (color[i] == 0) result.push_back(i - 1);
    return result;
}