【PTA数据结构 | C语言版】拓扑排序

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

题目

请编写程序，实现对有向无权图中的顶点进行拓扑排序的算法。
注意：如果拓扑序不唯一，输出任何一个序列都可以，由特殊裁判程序判定正确性。

输入格式：
输入首先在第一行给出两个正整数，依次为当前要创建的图的顶点数 n（≤100）和边数 m。
随后一行顺序给出 n 个顶点对应的字符串，由不超过 3 个英文字母或数字组成。
接下来 m 行，每行给出一条有向边的起点编号、终点编号。顶点编号从 0 开始。同行数字和字符串均以一个空格分隔。

输出格式：
参考样例。
首先在一行中输出 该图拓扑序存在性为 x，其中 x 为 1 表示该图顶点有拓扑序，为 0 表示没有。
随后在一行中按顶点拓扑序存输出每个顶点对应的字符串。为输出简单起见，每个字符串后有一个空格。
注意：如果拓扑序不存在，最后一行可以输出任何字符，均判为正确。

输入样例 1：
8 8
C0 C1 C2 C3 C4 C5 C6 C7
0 2
0 4
1 2
1 4
3 4
4 5
4 6
5 7

输出样例 1：
该图拓扑序存在性为 1
C0 C1 C3 C2 C4 C6 C5 C7

输入样例 2：
8 9
C0 C1 C2 C3 C4 C5 C6 C7
0 2
0 4
1 2
1 4
3 4
4 5
4 6
5 7
7 4

输出样例 2：

该图拓扑序存在性为 0
这里输出什么都不重要

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_VERTICES 100    // 最大顶点数
#define MAX_NAME_LENGTH 4   // 顶点名称最大长度（含字符串结束符）// 邻接表节点结构
typedef struct Node {int vertex;             // 顶点编号struct Node* next;      // 指向下一个邻接节点的指针
} Node;// 邻接表结构
typedef struct {Node* head;             // 邻接表的头指针
} AdjList;// 图结构
typedef struct {int n, m;               // 顶点数和边数char names[MAX_VERTICES][MAX_NAME_LENGTH]; // 顶点名称数组AdjList adj[MAX_VERTICES]; // 邻接表数组int in_degree[MAX_VERTICES]; // 每个顶点的入度
} Graph;// 创建新节点
Node* createNode(int v) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->vertex = v;newNode->next = NULL;return newNode;
}// 创建图
Graph* createGraph(int n, int m) {Graph* graph = (Graph*)malloc(sizeof(Graph));graph->n = n;graph->m = m;for (int i = 0; i < n; i++) {graph->adj[i].head = NULL;  // 初始化邻接表graph->in_degree[i] = 0;    // 初始化入度为0}return graph;
}// 添加有向边
void addEdge(Graph* graph, int src, int dest) {Node* newNode = createNode(dest);newNode->next = graph->adj[src].head;  // 插入到邻接表头部graph->adj[src].head = newNode;graph->in_degree[dest]++;  // 目标顶点入度加1
}// 拓扑排序主函数（Kahn算法）
int topologicalSort(Graph* graph, int* order) {int queue[MAX_VERTICES];  // 存储入度为0的顶点的队列int front = 0, rear = 0;  // 队列头尾指针int count = 0;            // 已排序顶点数// 初始化队列，将所有入度为0的顶点入队for (int i = 0; i < graph->n; i++) {if (graph->in_degree[i] == 0) {queue[rear++] = i;}}// 处理队列中的顶点while (front < rear) {int u = queue[front++];  // 取出队首顶点order[count++] = u;      // 加入拓扑排序结果// 遍历当前顶点的所有邻接顶点Node* current = graph->adj[u].head;while (current != NULL) {int v = current->vertex;graph->in_degree[v]--;  // 邻接顶点入度减1if (graph->in_degree[v] == 0) {queue[rear++] = v;  // 若入度变为0则入队}current = current->next;}}// 如果排序的顶点数等于总顶点数，则存在拓扑序return count == graph->n;
}int main() {int n, m;scanf("%d %d", &n, &m);  // 读取顶点数和边数Graph* graph = createGraph(n, m);  // 创建图// 读取顶点名称for (int i = 0; i < n; i++) {scanf("%s", graph->names[i]);}// 读取边信息并添加到图中for (int i = 0; i < m; i++) {int src, dest;scanf("%d %d", &src, &dest);addEdge(graph, src, dest);}int order[MAX_VERTICES];  // 存储拓扑排序结果// 执行拓扑排序并获取结果int hasTopologicalOrder = topologicalSort(graph, order);// 输出拓扑序存在性printf("该图拓扑序存在性为 %d\n", hasTopologicalOrder);// 输出拓扑排序结果（如果存在）if (hasTopologicalOrder) {for (int i = 0; i < n; i++) {printf("%s ", graph->names[order[i]]);}} else {printf("1");}printf("\n");return 0;
}