C语言根据输入的图的邻接矩阵A，判断此图的连通分量的个数。 【输入形式】 第一行为图的结点个数n，之后的n行为邻接矩阵的内容，每行n个数表示。其中A[i][j]=1表示两个结点邻接，而A[i][j]=0表示两个结点无邻接关系。 【输出形式】 输出此图连通分量的个数

以下是C语言代码实现：

#include <stdio.h>

#define MAX_N 100

int n, A[MAX_N][MAX_N], visited[MAX_N], cnt;

void dfs(int u) {
    visited[u] = 1;
    for (int v = 0; v < n; ++v) {
        if (A[u][v] && !visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &A[i][j]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i);
            ++cnt;
        }
    }
    printf("%d\n", cnt);
    0;
}

我们使用深度优先搜索（DFS）来遍历图，如果一个结点未被访问过，则说明它属于一个新的连通分量，我们从该结点开始进行 DFS，可以访问到的所有结点都属于同一个连通分量。最后，我们统计 DFS 的次数，即为连通分量的个数。

相关问题

问题描述】根据输入的图的邻接矩阵A，判断此图的连通分量的个数， 第一行为图的结点个数n，之后的n行为邻接矩阵的内容，每行n个数表示。其中A]=1表示两个结点邻接，而A[i]=0表示两个结点无邻接关系。【输出形式】输出此图连通分量的个数。写一个c语言代码

在C语言中，要计算给定邻接矩阵表示的图的连通分量个数，你可以使用深度优先搜索（DFS）或者广度优先搜索（BFS）算法。这里提供一个基于DFS的简单示例代码：

#include <stdio.h>
#include <stdbool.h>
#define MAX_N 100 // 图的最大节点数

// 用于表示图的邻接矩阵
bool adj[MAX_N][MAX_N];

// 邻接表辅助结构
typedef struct {
    int node;
    struct Node* next;
} Edge;

// 判断两个节点是否在同一连通分量
void dfs(int start, bool visited[], Edge** edges) {
    visited[start] = true;
    Edge* current = edges[start];
    while (current != NULL) {
        if (!visited[current->node]) {
            dfs(current->node, visited, edges);
        }
        current = current->next;
    }
}

// 找出所有连通分量并返回数量
int count_connected_components(int n, int adj_matrix[]) {
    int components = 0;
    bool visited[n + 1];
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            ++components;
            dfs(i, visited, edges); // 边存储在edges数组中，初始化为NULL
            Edge* edge = NULL;
            for (int j = 1; j <= n; j++) {
                if (adj[i][j] == 1) {
                    edge = (Edge*)malloc(sizeof(Edge));
                    edge->node = j;
                    edge->next = NULL;
                    edges[i] = edge;
                }
            }
        }
    }
    return components;
}

// 主函数，接受输入并输出结果
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &adj[i+1][j+1]);
        }
    }

    Edge* edges[MAX_N]; // 初始化边缘列表
    int components = count_connected_components(n, adj);

    printf("图中有 %d 个连通分量.\n", components);

    return 0;
}

注意，这个代码假设你已经将输入的邻接矩阵转换成了边的形式，并存储在`edges`数组中。如果直接给出的是邻接矩阵，你需要先将其转换成邻接表结构。

C语言根据输入的无向图的邻接矩阵A，判断此图的连通分量的个数。请使用邻接矩阵的存储结构创建图的存储，并采用BFS遍历算法实现，否则不得分。 【输入形式】 第一行为图的结点个数n，之后的n行为邻接矩阵的内容，每行n个数表示。其中A[i][j]=1表示两个结点邻接，而A[i][j]=0表示两个结点无邻接关系。 【输出形式】 输出此图连通分量的个数。

以下是C语言代码实现：

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

#define MAXN 100
#define QUEUE_SIZE 100

int A[MAXN][MAXN];  // 邻接矩阵
int visited[MAXN];  // 记录结点是否被访问过

// 定义队列结构体
struct Queue {
    int data[QUEUE_SIZE];
    int front;
    int rear;
};

// 初始化队列
void initQueue(struct Queue *q) {
    q->front = 0;
    q->rear = 0;
}

// 判断队列是否为空
int isQueueEmpty(struct Queue *q) {
    return q->front == q->rear;
}

// 入队
void enqueue(struct Queue *q, int x) {
    if ((q->rear + 1) % QUEUE_SIZE == q->front) {
        printf("Queue is full!\n");
        exit(1);
    }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % QUEUE_SIZE;
}

// 出队
int dequeue(struct Queue *q) {
    if (isQueueEmpty(q)) {
        printf("Queue is empty!\n");
        exit(1);
    }
    int x = q->data[q->front];
    q->front = (q->front + 1) % QUEUE_SIZE;
    return x;
}

// BFS遍历连通分量
void BFS(int v, int n) {
    struct Queue q;
    initQueue(&q);
    visited[v] = 1;  // 标记结点v已被访问
    enqueue(&q, v);  // 将结点v入队
    while (!isQueueEmpty(&q)) {
        int u = dequeue(&q);  // 取出队头结点
        for (int i = 0; i < n; i++) {
            if (A[u][i] && !visited[i]) {  // 如果结点i与结点u相邻且未被访问
                visited[i] = 1;  // 标记结点i已被访问
                enqueue(&q, i);  // 将结点i入队
            }
        }
    }
}

// 统计连通分量的个数
int countConnectedComponents(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {  // 如果结点i未被访问
            count++;  // 连通分量个数加1
            BFS(i, n);  // 遍历结点i所在的连通分量
        }
    }
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &A[i][j]);
        }
    }
    printf("The number of connected components is %d.\n", countConnectedComponents(n));
    return 0;
}

代码中使用了邻接矩阵存储图，用visited数组记录每个结点是否被访问过。BFS遍历连通分量时，使用了队列数据结构。最后统计连通分量的个数，即为所求。