Make It Connected

题意翻译

- 给定一张无向图。 - 每次操作你可以选择一个点 $x$. - 对于所有 $y\neq x$，如果 $(x,y)$ 之间有边则删去这条边，不然加入这条边。 - 求至少需要几次操作才能使得图联通，并且构造方案。 - 多测，$\sum n\leq 4000$。

题目描述

You are given a simple undirected graph consisting of $ n $ vertices. The graph doesn't contain self-loops, there is at most one edge between each pair of vertices. Your task is simple: make the graph connected. You can do the following operation any number of times (possibly zero): - Choose a vertex $ u $ arbitrarily. - For each vertex $ v $ satisfying $ v\ne u $ in the graph individually, if $ v $ is adjacent to $ u $ , remove the edge between $ u $ and $ v $ , otherwise add an edge between $ u $ and $ v $ . Find the minimum number of operations required to make the graph connected. Also, find any sequence of operations with the minimum length that makes the graph connected.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1\leq t\leq 800 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2\leq n\leq 4000 $ ) — the number of vertices in the graph. Then $ n $ lines follow. The $ i $ -th row contains a binary string $ s_i $ of length $ n $ , where $ s_{i,j} $ is '1' if there is an edge between vertex $ i $ and $ j $ initially, otherwise $ s_{i,j} $ is '0'. It is guaranteed that $ s_{i,i} $ is always '0' and $ s_{i,j}=s_{j,i} $ for $ 1\leq i,j\leq n $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 4000 $ .

输出格式

For each test case, in the first line, output an integer $ m $ — the minimum number of operations required. If $ m $ is greater than zero, then print an extra line consisting of $ m $ integers — the vertices chosen in the operations in your solution. If there are multiple solutions with the minimum number of operations, print any.

输入输出样例

输入样例 #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

说明

In the first test case, the graph is connected at the beginning, so the answer is $ 0 $ . In the second test case, if we do the operation with vertex $ 1 $ , we will get the following graph represented by an adjacency matrix: $$ \begin{bmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{bmatrix} $$ It's obvious that the graph above is connected. In the third test case, if we do the operation with vertex $ 3 $ and $ 4 $ , we will get the following graph represented by an adjacency matrix: $$ \begin{bmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{bmatrix} $$ It's obvious that the graph above is connected, and it can be proven that we can't perform less than $2$ operations to make the graph connected.

题目大意：
给定一个简单无向图，包含n个顶点。图没有自环，每对顶点间最多有一条边。你的任务是使图联通。你可以进行任意次以下操作（可能为零次）：

- 随机选择一个顶点u。
- 对于图中的每个顶点v满足v≠u，如果v与u相邻，则删除u和v之间的边，否则在u和v之间添加一条边。

求使图联通所需的最小操作次数，并构造出操作序列。

输入输出数据格式：
输入格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤800）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数n（2≤n≤4000）——图中的顶点数量。

然后是n行，第i行包含一个长度为n的二进制字符串si，其中如果顶点i和j之间最初有边，则si,j是'1'，否则si,j是'0'。

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

输出格式：
对于每个测试用例，第一行输出一个整数m——所需的最小操作次数。

如果m大于零，则再打印一行，包含m个整数——你的解决方案中操作的顶点。如果有多个最小操作次数的解决方案，输出其中任何一个。题目大意： 给定一个简单无向图，包含n个顶点。图没有自环，每对顶点间最多有一条边。你的任务是使图联通。你可以进行任意次以下操作（可能为零次）： - 随机选择一个顶点u。 - 对于图中的每个顶点v满足v≠u，如果v与u相邻，则删除u和v之间的边，否则在u和v之间添加一条边。 求使图联通所需的最小操作次数，并构造出操作序列。 输入输出数据格式： 输入格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤800）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数n（2≤n≤4000）——图中的顶点数量。 然后是n行，第i行包含一个长度为n的二进制字符串si，其中如果顶点i和j之间最初有边，则si,j是'1'，否则si,j是'0'。 保证对于所有测试用例，n的总和不超过4000。 输出格式： 对于每个测试用例，第一行输出一个整数m——所需的最小操作次数。 如果m大于零，则再打印一行，包含m个整数——你的解决方案中操作的顶点。如果有多个最小操作次数的解决方案，输出其中任何一个。