UOJ Logo Universal Online Judge

UOJ

#461. 新年的Dog划分

附件下载 统计

这是一道交互题。

跳蚤们已经修好了$m$条道路连通了$n(n \ge 2)$只Dog(这些道路中无重边无自环)。但是它们马上发现了一个很大的问题,$n$只Dog中并不全是SingleDog,也有一些是DoubleDog。

Dog们给了跳蚤们一个提示:这$m$条道路中,每一条都连接的是一只SingleDog和一只DoubleDog。不存在一条道路连接两只SingleDog或者两只DoubleDog。即图是一张二分图。

现在跳蚤们需要你把这些Dog给划分出来。跳蚤们不直接告诉你这$m$条道路,而是给了你这样一个功能:你可以进行若干次询问。每次询问你告诉跳蚤们一些点对,这些点对对应一个道路的集合,跳蚤们将回答如果将$m$条道路中在这个集合的道路去掉之后这$n$只Dog是否仍然连通。注意道路 $ (x, y) $ 和 $ (y, x) $ 是等价的,一次询问中一条道路加入多次和加入一次的效果相同。

你需要在2000次询问内内找出所有的SingleDog或者DoubleDog(即输出二分图的一侧),或判断跳蚤们的提示是错误的(图不是二分图),在这个情况下返回空集。可以证明因为图连通且点数至少为2,二分图的一部分不可能是空集。

任务

你需要实现下面的过程:

std::vector<int> check_bipartite(int vsize);

其中 vsize 是Dog的数量,也就是题目描述中的 $ n $。

你可以调用以下过程和交互库进行交互:

bool query(std::vector<std::pair<int, int>> banned_edges);

其中 banned_edges 是一个包含点对的 vector,表示你要去掉的点对。当图仍然联通时返回值为true,否则为false。你必须保证所有点对合法,否则你将得到 0 分。所谓点对合法就是值点对中的每个编号都必须合法,且两个点不能相同

评测方式

评测程序示例将读入如下格式的输入数据:

第一行包括两个正整数 $ n $ 和 $ m $;

接下来 $ m $ 行,每行表示一条边的两个端点。

请注意点的编号从0开始

评测程序示例将输出如下格式的输出数据:

第一行一个非负整数,表示二分图一部分的点数,如果是0表示不是二分图。

接下来一行空格隔开的数表示二分图一侧的每个点。

请注意点的编号从0开始

样例一至样例四

见样例及交互库下载

限制与约定

对于所有数据,保证 $n - 1 \le m \le \frac{n (n - 1)}{2}$,且 $ 2 \le n \le 200 $。

Subtask 1 (13 分): $n\le 10$,保证图是二分图。

Subtask 2 (24 分): $n\le 40$,保证图是二分图。

Subtask 3 (30 分): $n\le 100$

Subtask 4 (33 分): $n\le 200$

交互式类型的题目怎么本地测试

在本题中,本地测试时可以将 graderlib.cppgrader.cpp 一起粘到提交程序之前。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例及交互库下载