题目描述

难度分:$2400$

输入$T(\leq 800)$表示$T$组数据。所有数据的$n$之和$\leq 4000$。

每组数据输入$n(2 \leq n \leq 4000)$和一个$n \times n$的01矩阵$g$。

$g$表示一个无向图的邻接矩阵，其中$g[i][j]=1$表示有一条边连接$i$和$j$。

保证$g[i][j]=g[j][i]$且$g[i][i]=0$。

有如下操作：

• 选择一个点$x$，对于其余每个点$y$，如果$x$和$y$有边，则删除，如果没有边，则添加一条连接$x$和$y$的边。

要使图是连通的，最少要操作多少次？输出操作次数和每次操作的$x$。顶点编号从$1$开始。

输入样例

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

输出样例

0
1
1
2
3 4 
3
2 5 6 

算法

分类讨论

很难，感觉应该属于结论题那一类题目，第一次见的话都不知道怎么讨论才能不重不漏地考虑所有情况。

按照如下顺序，依次判断：

1. 整个图只有一个连通块，那么无需操作，输出$0$。
2. 图中存在一个孤立点，那么只需对这个点操作，即可让整个图连通。
3. 只要图中存在一个不是团（完全子图）的连通块，那么只需对这个连通块的度最小的点操作。证明如下。
4. 图至少$3$个连通块（经过了$3$的过滤，此时所有连通块都是完全子图），那么只需操作两次，随便选两个在不同连通块的点。
5. 图只有两个连通块（经过了$3$的过滤，此时所有连通块都是完全子图），那么选其中点数少的连通块操作，操作次数就是该连通块的点数。

$3$的证明：

设这个度最小的点是$x$，设$x$所在连通分量为$V$。由于$V$不是团，所以$V$中的某些点在操作前不与$x$相连，在操作后会与$x$相连。

如果$x$不是割点，那么操作后，$V$不会分成更多的连通块，并且仍然有点连着$x$，所以整个图是连通的。

如果$x$是割点（例如两个三角形各有一个顶点连着$x$），首先来说明几个性质：

• 性质$1$：由于$x$的度数至少是$2$（割点性质），所以其余每个点的度数也至少是$2$，这意味着$V$中没有叶子。
• 性质$2$：删除$x$会把$V$分成若干个连通块，每个连通块至少有$3$个点（根据性质$1$）。

现在的问题是：操作后，每个连通块是否都有点与$x$相连？

反证法：假设有一个连通块$U$没有点与$x$相连，设这个连通块的大小为$|U|$。由于操作前$x$除了与这$|U|$个点相连外，还与其它点相连（注意我们假设$x$是割点），这说明$x$的度数至少是$|U|+1$，但由于$x$的度数最小，所以$|U|$中必定有度数至少为$|U|+1$的点，但$U$中只有$|U|$个点，度数不可能超过 $|U|$，矛盾。所以操作后，每个连通块都至少有一个点与$x$相连。

复杂度分析

时间复杂度

遍历完一遍图之后就可以$O(1)$进行分类讨论，输出每类结果的答案，因此算法的时间复杂度为$O(n)$。

空间复杂度

除去题目输入的邻接矩阵$g$。遍历图的时候需要判重数组$st$，防止重复经过同一个节点，规模为$O(n)$；节点的度数组$deg$，规模为$O(n)$；每个连通分量的节点集合$groups$，在最差情况下需要存满$n$个节点，规模为$O(n)$。所以算法整体的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 4010;
int t, n, deg[N];
char s[N][N];
bool st[N];

void dfs(int u, vector<int>& vs) {
    st[u] = true;
    vs.push_back(u);
    for(int v = 1; v <= n; v++) {
        if(!st[v] && s[u][v] == '1') {
            dfs(v, vs);
        }
    }
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            deg[i] = st[i] = 0;
        }
        for(int i = 1; i <= n; i++) {
            scanf("%s", s[i] + 1);
            for(int j = 1; j <= n; j++) {
                deg[i] += s[i][j] == '1'? 1: 0;
            }
        }
        vector<vector<int>> groups;
        bool flag = false;
        for(int i = 1; i <= n; i++) {
            if(st[i]) continue;
            vector<int> group;
            dfs(i, group);
            int m = group.size();
            if(m == n) {
                // 只有一个连通块
                puts("0");
                flag = true;
                break;
            }
            if(m == 1) {
                // 有一个孤立点
                puts("1");
                printf("%d\n", group[0]);
                flag = true;
                break;
            }
            int mn = group[0];
            for(int x: group) {
                if(deg[x] < deg[mn]) {
                    mn = x;
                }
            }
            if(deg[mn] < m - 1) {
                // 有一个节点的度不是m-1，当前连通块不是完全图
                puts("1");
                printf("%d\n", mn);
                flag = true;
                break;
            }
            groups.push_back(group);
        }
        if(!flag) {
            if(groups.size() > 2) {
                puts("2");
                printf("%d %d\n", groups[0][0], groups[1][0]);
            }else {
                if(groups[0].size() < groups[1].size()) {
                    printf("%d\n", (int)groups[0].size());
                    for(int x: groups[0]) {
                        printf("%d ", x);
                    }
                }else {
                    printf("%d\n", (int)groups[1].size());
                    for(int x: groups[1]) {
                        printf("%d ", x);
                    }
                }
                puts("");
            }
        }
    }
    return 0;
}