简答题
偏难
#19997
连通图
连通图



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 100005;
int n, m;
int f[N];
int ans;
// 带路径压缩的并查集查找
int getf(int u) {
if (!f[u])
return u;
return f[u] = getf(f[u]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
int fu = getf(u);
int fv = getf(v);
if (fu != fv) {
f[fu] = fv;
}
}
// 统计连通块数量:根节点数量
ans = 0;
for (int i = 1; i <= n; ++i) {
if (getf(i) == i)
ans++;
}
// 连通块数-1 = 最少需要添加的边(生成树边数)
printf("%d\n", ans - 1);
return 0;
}</pre>
这道题暂未补解析。