本專欄持續輸出數據結構題目集，歡迎訂閱。

題目

本題請你編寫程序，輸出給定有向圖中的各個強連通分量，并統計強連通分量的個數。

輸入格式：
輸入首先在第一行給出 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); // 輸出強連通分量個數
}