邻接表存储的无向图求连通分量个数并输出各连通分量的首顶点，完整代码c语言加算法思想

邻接表是一种常用的数据结构用于表示稀疏图，其中每个顶点都有一个链接到其相邻顶点的列表。求解无向图的连通分量个数以及每个连通分量的首顶点，可以采用深度优先搜索（DFS）或者广度优先搜索（BFS）算法。

以下是使用C语言实现的一个简单示例，这里我们选择使用DFS：

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

typedef struct {
    int vertex;
    struct Node *next;
} Node;

typedef struct Graph {
    int vertices;
    Node **adj;
} Graph;

void add_edge(Graph *graph, int src, int dest) {
    graph->adj[src] = (Node*)malloc(sizeof(Node));
    graph->adj[src]->vertex = dest;
    graph->adj[src]->next = NULL;
    if(dest != src){
        graph->adj[dest] = (Node*)malloc(sizeof(Node));
        graph->adj[dest]->vertex = src;
        graph->adj[dest]->next = NULL;
    }
}

void DFSvisit(int vertex, bool visited[], Graph *graph, int *component) {
    visited[vertex] = true;
    *component += 1; //标记当前连通分量

    Node *temp = graph->adj[vertex];
    while(temp != NULL) {
        if(!visited[temp->vertex]) {
            DFSvisit(temp->vertex, visited, graph, component);
        }
        temp = temp->next;
    }
}

int count_connected_components(Graph *graph) {
    int num_components = 0;
    int* visited = malloc(graph->vertices * sizeof(bool));
    for(int i = 0; i < graph->vertices; i++) {
        visited[i] = false;
    }

    for(int i = 0; i < graph->vertices; i++) {
        if(!visited[i]) { // 如果节点未访问过
            DFSvisit(i, visited, graph, &num_components); // 开始从i开始做DFS
        }
    }

    free(visited);
    return num_components;
}

int main() {
    Graph g;
    int num_vertices;
    printf("Enter number of vertices: ");
    scanf("%d", &num_vertices);
    g.vertices = num_vertices;
    g.adj = (Node**)malloc(num_vertices * sizeof(Node*));

    int u, v;
    printf("Enter edges (source vertex then destination vertex): \n");
    for(int i = 0; i < num_vertices - 1; i++) {
        scanf("%d %d", &u, &v);
        add_edge(&g, u, v);
    }

    int components = count_connected_components(&g);
    printf("\nNumber of connected components: %d\n", components);

    // 输出每个连通分量的首顶点
    for(int i = 0; i < components; i++) {
        int start_vertex = -1;
        for(int j = 0; j < num_vertices; j++) {
            if(g.adj[j] && !g.adj[j]->next) {
                start_vertex = j;
                break;
            }
        }
        printf("Component %d: Vertex %d\n", i+1, start_vertex);
    }

    return 0;
}

在这个代码里，首先构建了一个无向图，然后通过`count_connected_components`函数使用DFS遍历图，并记录连通分量的数量。最后，遍历整个邻接表找出每个连通分量的第一个顶点。