CF1738F Connectivity Addicts

这是一个交互题。 给定一个有 $n$ 个顶点的简单无向图，顶点编号为 $1$ 到 $n$，你的任务是对所有顶点进行染色，使得对于每种颜色 $c$，满足以下条件： 1. 所有被染为颜色 $c$ 的顶点集合是连通的； 2. $s_c \leq n_c^2$，其中 $n_c$ 表示被染为颜色 $c$ 的顶点数，$s_c$ 表示这些顶点的度数之和。 可以证明，总是存在一种染色方式使上述条件成立。最初，你只知道顶点数 $n$ 以及每个顶点的度数。 在每次查询中，你可以选择一个顶点 $u$。作为回应，如果这是你对顶点 $u$ 的第 $k$ 次查询，你将获得与 $u$ 相连的第 $k$ 条边的另一个端点。 你最多可以进行 $n$ 次查询。 一个无向图是简单图，表示它没有重边和自环。 顶点的度数是与其相连的边的数量。 一个顶点集合 $S$ 是连通的，表示对于 $S$ 中任意两个不同的顶点 $u, v$，存在一条仅经过 $S$ 中顶点的路径连接 $u$ 和 $v$。即，存在一系列边 $(u_1, v_1), (u_2, v_2), \dots, (u_k, v_k)$，其中 $k \geq 1$，满足： 1. $u_1 = u$，$v_k = v$，且对于每个 $1 \leq i < k$，有 $v_i = u_{i+1}$； 2. 对于每个 $1 \leq i \leq k$，$u_i \in S$ 且 $v_i \in S$。 特别地，只包含一个顶点的集合也是连通的。

每个测试包含多组数据。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。接下来的若干行描述每个测试用例及其交互过程。 对于每个测试用例，你首先读入一行一个整数 $n$（$1 \leq n \leq 1000$），表示图的顶点数。 第二行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$（$0 \leq d_i \leq n-1$），其中 $d_i$ 表示第 $i$ 个顶点的度数。 你可以对顶点 $u$（$1 \leq u \leq n$）发起一次查询，输出 - "? $u$" 单独占一行。如果这是你对顶点 $u$ 的第 $k$ 次查询，接下来会收到一个整数 $e_{u, k}$，表示与 $u$ 相连的第 $k$ 条边的另一个端点。如果 $k > d_u$，则 $e_{u, k} = -1$。你最多只能进行 $n$ 次 "?" 查询。最终输出答案时，输出 - "! $c_1$ $c_2$ $\dots$ $c_n$" 单独占一行，其中 $c_i$（$1 \leq c_i \leq n$）表示第 $i$ 个顶点的颜色。之后程序应继续处理下一个测试用例，或在最后一个测试用例后终止。保证输入的图是简单无向图。 保证所有测试用例中 $n$ 的总和不超过 $1000$。 如果你的查询格式不合法，或查询次数超过 $n$，你将收到 Wrong Answer 判定。 每次输出查询后，别忘了输出换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 Hack 的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例数量。接下来每个测试用例的描述如下。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示图的顶点数。 接下来 $n$ 行，第 $i$ 行包含一个整数 $d_i$（$0 \leq d_i \leq n-1$），以及 $d_i$ 个不同的整数 $e_{i,1}, e_{i,2}, \dots, e_{i,d_i}$（$1 \leq e_{i,j} \leq n$ 且 $e_{i,j} \neq i$），表示与 $i$ 相连的第 $j$ 条边的另一个端点。 保证输入的图是简单无向图。 保证所有测试用例中 $n$ 的总和不超过 $1000$。

见输入格式说明。

在样例中，只有一个测试用例。 该测试用例中，$n = 5$ 个顶点，其中顶点 $1, 2, 3, 4$ 的度数为 $2$，顶点 $5$ 的度数为 $0$。显然，顶点 $5$ 是孤立点，即它不与其他顶点相连。 一个可能的交互过程如下：对顶点 $1$ 查询两次，对顶点 $3$ 查询两次，共进行了 $4$ 次 "?" 查询。根据这些查询的回复，我们知道顶点 $1$ 和顶点 $3$ 都分别与顶点 $2$ 和 $4$ 相连。 一种可能的染色方案如下：顶点 $1$ 和 $2$ 染为颜色 $1$，顶点 $3$ 和 $4$ 染为颜色 $2$，顶点 $5$ 染为颜色 $3$。可以验证该方案满足要求： - 对于颜色 $c = 1$，顶点 $1$ 和 $2$ 连通，且 $n_1 = 2$，$s_1 = d_1 + d_2 = 2 + 2 = 4 \leq n_1^2 = 2^2 = 4$； - 对于颜色 $c = 2$，顶点 $3$ 和 $4$ 连通，且 $n_2 = 2$，$s_2 = d_3 + d_4 = 2 + 2 = 4 \leq n_2^2 = 2^2 = 4$； - 对于颜色 $c = 3$，只有顶点 $5$ 染为颜色 $3$，且 $n_3 = 1$，$s_3 = d_5 = 0 \leq n_3^2 = 1^2 = 1$。 由 ChatGPT 4.1 翻译