← 返回题目列表

Codeforces · 1761/E

E. 使其连接

中文机器翻译题面 查看原题

给你一个简单的无向图,由 $$$n$$$ 个顶点组成。该图不包含自环,每对顶点之间最多有一条边。您的任务很简单:将图表连接起来。

您可以执行以下操作任意次数(可能为零):

- 任意选择一个顶点$$$u$$$。
- 对于图中单独满足 $$$v\ne u$$$ 的每个顶点 $$$v$$$,如果 $$$v$$$ 与 $$$u$$$ 相邻,则删除 $$$u$$$ 和 $$$v$$$ 之间的边,否则在 $$$u$$$ 和 $$$v$$$ 之间添加一条边。

求使图连通所需的最少操作数。另外,找到使图连通的最小长度的任意操作序列。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 800$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 4000$$$) — 图中的顶点数。

然后是 $$$n$$$ 行。第 $$$i$$$ 行包含长度为 $$$n$$$ 的二进制字符串 $$$s_i$$$,其中如果顶点 $$$i$$$ 和 $$$j$$$ 之间最初存在边,则 $$$s_{i,j}$$$ 为“1”,否则 $$$s_{i,j}$$$ 为“0”。

保证 $$$s_{i,i}$$$ 始终为 '0' 并且 $$$s_{i,j}=s_{j,i}$$$ 对于 $$$1\leq i,j\leq n$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$4000$$$。

输出

对于每个测试用例,在第一行中输出一个整数 $$$m$$$ — 所需的最小操作数。

如果 $$$m$$$ 大于零,则打印由 $$$m$$$ 整数组成的额外行 - 在解决方案的操作中选择的顶点。如果有多个具有最少操作次数的解决方案,则打印任何一个。

示例

输入 #1

4
3
011
100
100
3
000
001
010
4
0100
1000
0001
0010
6
001100
000011
100100
101000
010001
010010

输出 #1

0
1
1
2
3 4 
3
2 5 6

注意

在第一个测试用例中,图形从一开始就是连接的,所以答案是$$$0$$$。

在第二个测试用例中,如果我们对顶点 $$$1$$$ 进行运算,我们将得到以下由邻接矩阵表示的图:

$$$$$$ \begin{bmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{bmatrix} $$$$$$

很明显,上图是连通的。

在第三个测试用例中,如果我们对顶点 $$$3$$$ 和 $$$4$$$ 进行运算,我们将得到以下由邻接矩阵表示的图:

$$$$$$ \begin{bmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{bmatrix} $$$$$$

很明显,上面的图是连通的,并且可以证明我们不能执行少于 $$$2$$$ 的操作来使图连通。