本文共 1346 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要计算给定图中的连通块数量，并减去1。连通块是指图中由边直接或间接连接的点构成的集合。

方法思路

我们可以使用并查集（Disjoint Set Union，DSU）来高效地计算连通块的数量。具体步骤如下：

这种方法的时间复杂度接近线性，可以高效处理大规模图。

解决代码

#include 
   
    using namespace std;int main() {    int n, m;    scanf("%d %d", &n, &m);    vector
    
      parent(n + 1);    vector
     
       size(n + 1);    for (int i = 1; i <= n; ++i) {        parent[i] = i;        size[i] = 1;    }    for (int i = 1; i <= m; ++i) {        int u, v;        scanf("%d %d", &u, &v);        int root_u = find(u);        int root_v = find(v);        if (root_u != root_v) {            if (size[root_u] < size[root_v]) {                parent[root_u] = root_v;                size[root_v] += size[root_u];            } else {                parent[root_v] = root_u;                size[root_u] += size[root_v];            }        }    }    int count = 0;    for (int i = 1; i <= n; ++i) {        if (find(i) == i) {            count++;        }    }    cout << count - 1 << endl;}// 并查集查找函数int find(int x) {    if (parent[x] != x) {        parent[x] = find(parent[x]);    }    return parent[x];}
     
    
   

代码解释

这种方法高效且正确，适用于大规模图，能够快速解决问题。

转载地址：http://moewz.baihongyu.com/