给定一个无向图，判断该图是否是连通图，并输出连通分支数。

输入：顶点，边。

输出：是否是连通图（Yes/No），连通分支数（1/2/3...）。

#include <stdio.h>

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵
int visited[MAX_VERTICES];  // 记录节点是否被访问过

// 深度优先搜索
void dfs(int v, int n) {
    visited[v] = 1;  // 标记当前节点为已访问
    for (int i = 0; i < n; i++) {
        if (graph[v][i] == 1 && !visited[i]) {  // 如果邻接且未访问过
            dfs(i, n);
        }
    }
}

// 判断图是否连通，并返回连通分支的数量
int countConnectedComponents(int n) {
    int components = 0;
    for (int i = 0; i < n; i++) {
        visited[i] = 0;  // 初始化visited数组
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, n);  // 从未访问过的节点开始DFS
            components++;  // 每次DFS调用表示发现了一个新的连通分支
        }
    }

    return components;
}

int main() {
    int n;

    // 输入顶点数
    printf("请输入顶点数: ");
    scanf("%d", &n);

    // 输入邻接矩阵
    printf("请输入邻接矩阵:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    // 计算并输出连通分支数
    int components = countConnectedComponents(n);
    printf("图的连通分支数: %d\n", components);

    // 判断图是否连通
    if (components == 1) {
        printf("该图是连通图。\n");
    } else {
        printf("该图不是连通图。\n");
    }

    return 0;
}