C语言【问题描述】 给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写程序来计算无向图中连通分量的数目。要求以邻接矩阵方式存储图。 【输入形式】 顶点数目 边数目 边列表 【输出形式】 连通分量的数目 【样例输入】 5 3 0 1 1 2 3 4 【样例输出】 2 【样例输入】 5 4 0 1 1 2 2 3 3 4 【样例输出】 1

以下是基于邻接矩阵的图连通性计算算法的 C 语言实现：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000

int graph[MAXN][MAXN]; // 邻接矩阵
int visited[MAXN]; // 标记数组

// DFS 遍历图，标记当前连通分量的所有结点
void dfs(int u, int n) {
    visited[u] = 1; // 标记当前结点已访问
    for (int v = 0; v < n; v++) {
        if (graph[u][v] && !visited[v]) { // 如果 u 和 v 有边，并且 v 未被访问
            dfs(v, n); // 递归访问 v
        }
    }
}

// 计算连通分量的数目
int count_components(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) { // 如果结点 i 未被访问，则说明它属于一个新的连通分量
            dfs(i, n); // DFS 标记当前连通分量的所有结点
            count++; // 连通分量数目加一
        }
    }
    return count;
}

int main() {
    int n, m, u, v;
    scanf("%d %d", &n, &m);
    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
        visited[i] = 0;
    }
    // 读入边
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
        graph[v][u] = 1; // 无向图要加上反向边
    }
    // 计算连通分量的数目
    int count = count_components(n);
    printf("%d\n", count);
    return 0;
}

算法的思路是使用 DFS 遍历图，从一个未被访问的结点开始，递归地访问所有与之连通的结点，并标记它们为已访问。然后继续寻找下一个未被访问的结点，直到所有结点都被访问过。visited 数组用于标记已访问的结点，避免重复访问和死循环。时间复杂度为 O(n^2)，其中 n 为顶点个数。