算法实现求无向连通图的连通分量数

我们可以使用深度优先搜索（DFS）算法来求无向连通图的连通分量数。具体实现步骤如下：

1. 初始化一个变量count，用于记录连通分量数，初始值为0。
2. 创建一个布尔数组visited，用于记录每个节点是否被访问过，初始值为false。
3. 对于图中的每个未被访问过的节点，执行以下步骤：
1. 将当前节点标记为已访问。
2. 递归访问当前节点的所有未被访问的邻居节点。
3. 递归访问结束后，将count加1，表示发现了一个新的连通分量。
4. 返回count，即为无向连通图的连通分量数。

以下是使用C++实现的示例代码：

#include <iostream>
#include <vector>
using namespace std;

void dfs(int u, vector<bool>& visited, vector<vector<int>>& adj) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, visited, adj);
        }
    }
}

int countConnectedComponents(vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, visited, adj);
            count++;
        }
    }
    return count;
}

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入一条边的两个端点
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图需要双向加边
    }
    int count = countConnectedComponents(adj); // 求连通分量数
    cout << count << endl;
    return 0;
}

其中，adj是邻接表表示的无向图，adj[u]表示与节点u相邻的所有节点。输入格式为第一行两个整数n和m，分别表示节点数和边数；接下来m行每行两个整数u和v，表示一条边的两个端点。输出无向连通图的连通分量数。