简答题 偏难
#19997

连通图

连通图

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include &lt;algorithm&gt; #include &lt;cstdio&gt; 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", &amp;n, &amp;m);     for (int i = 1; i &lt;= m; ++i) {         int u, v;         scanf("%d%d", &amp;u, &amp;v);         int fu = getf(u);         int fv = getf(v);         if (fu != fv) {             f[fu] = fv;         }     }     // 统计连通块数量:根节点数量     ans = 0;     for (int i = 1; i &lt;= n; ++i) {         if (getf(i) == i)             ans++;     }     // 连通块数-1 = 最少需要添加的边(生成树边数)     printf("%d\n", ans - 1);     return 0; }</pre>
这道题暂未补解析。