本专栏持续输出数据结构题目集，欢迎订阅。

题目

本题请你编写程序，输出给定有向图中的各个强连通分量，并统计强连通分量的个数。

输入格式：
输入首先在第一行给出 2 个整数，依次为有向图的顶点数 n（0<n≤15）和边数 m。
随后 m 行，每行给出一条有向边的起点和终点编号。编号从 0 开始，其间以 1 个空格分隔。

输出格式：
按照 { v1 v2 … vk } 的格式，每行输出一个强连通分量中的所有顶点 v1~vk 的编号。最后一行输出强连通分量的个数。

输入样例：
4 5
0 1
1 3
3 0
2 1
2 3

输出样例：
{ 0 1 3 }
{ 2 }
2

注意：强连通分量的输出顺序是不唯一的，以任何顺序输出都可以，有特殊裁判程序判断输出的正确性。例如下列输出也是正确的。

{ 2 }
{ 1 3 0 }
2

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_VERTEX 15typedef struct Node {int vertex;struct Node* next;
} Node;typedef struct {Node* adj[MAX_VERTEX];int n;
} Graph;// 栈结构用于DFS顺序记录
typedef struct {int data[MAX_VERTEX];int top;
} Stack;// 函数声明
void initGraph(Graph* g, int n);
void addEdge(Graph* g, int src, int dest);
Graph getTranspose(Graph* g);
void DFSUtil(Graph* g, int v, int visited[], Stack* stack);
void fillOrder(Graph* g, int visited[], Stack* stack);
void printSCCs(Graph* g);int main() {int n, m;scanf("%d %d", &n, &m);Graph g;initGraph(&g, n);for (int i = 0; i < m; i++) {int src, dest;scanf("%d %d", &src, &dest);addEdge(&g, src, dest);}printSCCs(&g);return 0;
}// 初始化图
void initGraph(Graph* g, int n) {g->n = n;for (int i = 0; i < n; i++) {g->adj[i] = NULL;}
}// 添加有向边
void addEdge(Graph* g, int src, int dest) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->vertex = dest;newNode->next = g->adj[src];g->adj[src] = newNode;
}// 获取图的转置（所有边反向）
Graph getTranspose(Graph* g) {Graph transpose;initGraph(&transpose, g->n);for (int v = 0; v < g->n; v++) {Node* temp = g->adj[v];while (temp != NULL) {addEdge(&transpose, temp->vertex, v);temp = temp->next;}}return transpose;
}// 初始化栈
void initStack(Stack* s) {s->top = -1;
}// 入栈
void push(Stack* s, int v) {s->data[++(s->top)] = v;
}// 出栈
int pop(Stack* s) {return s->data[(s->top)--];
}// 判断栈是否为空
int isEmpty(Stack* s) {return s->top == -1;
}// 深度优先搜索辅助函数
void DFSUtil(Graph* g, int v, int visited[], Stack* stack) {visited[v] = 1;Node* temp = g->adj[v];while (temp != NULL) {int adjVertex = temp->vertex;if (!visited[adjVertex]) {DFSUtil(g, adjVertex, visited, stack);}temp = temp->next;}// 记录顶点完成时间（压栈）if (stack != NULL) {push(stack, v);} else {// 直接输出SCC成员（第二次DFS）printf("%d ", v);}
}// 填充顶点处理顺序（第一次DFS）
void fillOrder(Graph* g, int visited[], Stack* stack) {for (int i = 0; i < g->n; i++) {if (!visited[i]) {DFSUtil(g, i, visited, stack);}}
}// 打印所有强连通分量
void printSCCs(Graph* g) {Stack stack;initStack(&stack);int visited[MAX_VERTEX];memset(visited, 0, sizeof(visited));// 第一次DFS，记录顶点处理顺序fillOrder(g, visited, &stack);// 获取图的转置Graph transpose = getTranspose(g);// 重置访问标记memset(visited, 0, sizeof(visited));int count = 0; // 强连通分量计数器// 第二次DFS，处理转置图while (!isEmpty(&stack)) {int v = pop(&stack);if (!visited[v]) {printf("{ ");DFSUtil(&transpose, v, visited, NULL);printf("}\n");count++;}}printf("%d\n", count); // 输出强连通分量个数
}