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

无向图的连通分量是指图中所有顶点可以通过边连接起来的子图。连通分量的数量取决于图中是否存在多个互不相连的部分。以下是解决这个问题的详细步骤：

1. 输入处理

首先，读取输入数据，包括顶点数和边数。然后读取顶点信息，接着读取每条边的信息。

• 顶点数和边数：第一行输入顶点数和边数，使用空格分隔。
• 顶点信息：第二行输入每个顶点的信息，按顺序排列。
• 边信息：第三行输入每条边的信息，每条边以空格分隔两个顶点编号。

2. 邻接矩阵初始化

创建一个邻接矩阵，大小为顶点数×顶点数，初始值为False。对于每条边，设置对应的邻接矩阵位置为True。

3. 连通分量计算

使用广度优先搜索（BFS）或深度优先搜索（DFS）遍历图，标记访问过的顶点。当发现一个未访问的顶点时，启动一次遍历，计数加一，直到所有顶点都被访问。

4. 返回结果

输出连通分量的数量。

代码示例

#include 
   
    #include 
    
     using namespace std;int main() {    int vertex_num, edge_num;    cin >> vertex_num >> edge_num;        vector
     
      
       > adjacency(vertex_num, vector
       
        (vertex_num, false));        // 处理顶点信息    string vertex_info;    getline(cin, vertex_info);    for (int i = 0; i < vertex_num; ++i) {        char c = vertex_info[i];        // 假设顶点是A、B等对应字符，转换为数字索引        int idx = i; // 假设每个字符对应索引        adjacency[idx][idx] = true; // 每个顶点自环？    }        // 处理边信息    string edge_info;    getline(cin, edge_info);    size_t pos = 0;    for (size_t i = 0; i < edge_num; ++i) {        // 假设边信息以空格分隔，每条边两个顶点        size_t end = edge_info.find(' ', pos);        if (end == string::npos) end = edge_info.size();        string u_str = edge_info.substr(pos, end - pos);        string v_str = edge_info.substr(end + 1);        int u = u_str[0] - 'A';        int v = v_str[0] - 'A';        adjacency[u][v] = true;        adjacency[v][u] = true;        pos = end + 2;    }        // 标记访问状态    vector
        
          visited(vertex_num, false); int component_count = 0; // 广度优先搜索 for (int i = 0; i < vertex_num; ++i) { if (!visited[i]) { component_count++; // BFS遍历 queue
         
           q; q.push(i); visited[i] = true; while (!q.empty()) { int current = q.front(); q.pop(); for (int neighbor = 0; neighbor < vertex_num; ++neighbor) { if (adjacency[current][neighbor] && !visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } } cout << component_count << endl; return 0;}
         
        
       
      
     
    
   

代码解释

通过这种方法，可以准确地计算出无向图的连通分量数目。