PinelyRound1(Div.1+Div.2)-连通图构建问题（逻辑分析/并查集+分类讨论）

问题描述

给定一个包含最多4000个节点的无向图，图中不存在自环或多重边。

允许进行的操作包括：选择任一节点u，对于除u外的每一个节点v，如果u和v当前已直接相连，则断开该边；反之，则添加一条连接u和v的边。

目标是计算最少需要执行上述操作多少次才能使整个图变为连通状态，并指出需要操作的具体节点编号。

注意，测试案例总数不超过800组，所有案例中节点总数之和不超过4000。

解题思路

本题解基于官方题解和社区贡献代码整理而成。

解决方案

针对不同情况，采取相应的策略：

1. 如果图本身就是一个连通块，无需任何操作，答案为0。

2. 存在一个孤立节点时，只需将其与其他所有节点连接起来，答案为1，输出该孤立节点的编号。

3. 当存在至少一个非完全连通的子图时，可以通过操作该子图中度数最小的节点x，使其与原子图保持连通的同时，与其它子图建立连接，答案同样为1，输出节点x的编号。

4. 若图由两个完全连通的子图组成，需将较小的子图完全拆散，以便与较大的子图合并，答案等于较小子图中的节点数，输出这些节点的编号。

5. 对于三个或更多完全连通的子图，先从任意一个子图中选取一点进行操作，再从另一个子图中选择另一点操作，确保所有子图最终实现连通，答案固定为2，输出两次操作所选的节点编号。

技巧分享

对于第三种情况，关键在于理解为何选择度数最小的节点x进行操作可以保证图的连通性。这涉及到一个重要的引理：在一个非完全连通的子图中，度数最小的节点x，通过反转其所有邻接关系后，图仍保持连通。此引理可通过分析x是否为割点及其与其它节点的连接特性来证明。

代码实现

以下是C++语言的实现代码，用于解决上述问题：

#include
using namespace std;
typedef long long ll;
const int maxn = 4005;
int t, n, u, v, par[maxn], sz[maxn], deg[maxn];
char s[maxn];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void solve() {
    int ans = 0, now = n, pos = -1;
    for (int i = 0; i         if (find(i) == i) {
            ans++;
            if (now > sz[i]) {
                now = sz[i];
                pos = i;
            }
        }
    }
    if (ans == 1) {
        puts("0");
        return;
    }
    for (int i = 0; i         int f = find(i);
        if (f == i && sz[i] == 1) {
            puts("1");
            printf("%d\n", i + 1);
            return;
        }
        if (sz[f] - 1 != deg[i]) {
            int mx = n, id = -1;
            for (int j = 0; j                 if (find(j) == f) {
                    if (mx > deg[j]) {
                        mx = deg[j];
                        id = j;
                    }
                }
            }
            puts("1");
            printf("%d\n", id + 1);
            return;
        }
    }
    if (ans == 2) {
        printf("%d\n", sz[pos]);
        for (int i = 0; i             if (find(i) == pos) {
                printf("%d ", i + 1);
            }
        }
        puts("");
        return;
    } else {
        int cnt = 0;
        puts("2");
        for (int i = 0; i             if (find(i) == i) {
                printf("%d ", i + 1);
                cnt++;
                if (cnt == 2) {
                    puts("");
                    return;
                }
            }
        }
    }
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int j = 0; j             par[j] = j;
            sz[j] = 1;
            deg[j] = 0;
        }
        for (int j = 0; j             scanf("%s", s);
            for (int k = 0; k                 if (s[k] == '1') {
                    deg[k]++;
                    deg[j]++;
                    int a = find(j), b = find(k);
                    if (a == b) continue;
                    sz[a] += sz[b];
                    par[b] = a;
                }
            }
        }
        solve();
    }
    return 0;
}